File IntervalCover.h

↰ Parent directory (ADS/optimization)

The cover of a segment by intervals: among n closed intervals [ a_i , b_i ], the fewest whose union contains the segment [ lo , hi ], e.g.

Definition (ADS/optimization/IntervalCover.h)

Detailed Description

the sprinklers at D_i of radius R_i, of intervals [ D_i - R_i , D_i + R_i ], that water a lawn [ 0 , L ].

The greedy choice of chapter 14: with the part [ lo , x ] already covered, among the intervals that start at x or before take the one that ends farthest; if none goes past x the point just after x stays uncovered and there is no cover. An exchange argument shows that some optimal cover begins with the greedy interval: the interval of an optimal cover that contains x ends no farther. On the intervals sorted by left end, one scan suffices, O( n log n ) time for the sort.

The problem is the dual of the independent set of intervals [see File Intervals.h], and the one-dimensional case of the set cover, which in general is NP-hard and approximated within :math:` ln n ` by the greedy on the most new elements (Chvatal).

The contracts [see File Contract.h]: lo < hi and a_i <= b_i; the intervals chosen cover [ lo , hi ] (checked at level 3). The functions are defined in IntervalCover.tpp.

  1. Montresor, Algoritmi e Strutture Dati, 2025, chapter 14, https://algoritmicamente.it/materiali/libro/capitoli/cap14.pdf

  1. Kleinberg, E. Tardos, Algorithm Design, Addison-Wesley, 2005, section 4.1

  1. Chvatal, A greedy heuristic for the set-covering problem, Mathematics of Operations Research 4(3), 233-235, 1979, doi:10.1287/moor.4.3.233

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions