Demand Hitting and Covering of Intervals

Hitting and Covering problems have been extensively studied in the last few decades and have applications in diverse areas. While the hitting and covering problems are NP-hard for most settings, they are polynomial solvable for intervals. Demand hitting is a generalization of the hitting problem, where there is an integer demand associated with each object, and the demand hitting set must contain at least as many points as the demand of each object. In this paper, we consider the demand hitting and covering problems for intervals that have no containment. For the unweighted setting, we give a simple greedy algorithm. In the weighted setting, we model this problem as a min-cost max flow problem using a non-trivial reduction and solve it using standard flow algorithms.