Advertisement
Published in:
2017 | OriginalPaper | Chapter
Demand Hitting and Covering of Intervals
Authors : Datta Krupa R., Aniket Basu Roy, Minati De, Sathish Govindarajan
Published in: Algorithms and Discrete Applied Mathematics
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
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.