Generalization of Hitting, Covering and Packing Problems on Intervals
Abstract
Interval graphs are well studied structures. Intervals can represent resources like jobs to be scheduled. Finding maximum independent set in interval graphs would correspond to scheduling maximum number of nonconflicting jobs on the computer. Most optimization problems on interval graphs like independent set, vertex cover, dominating set, maximum clique, etc can be solved eﬃciently using combinatorial algorithms in polynomial time. Hitting, Covering and Packing problems have been extensively studied in the last few decades and have applications in diverse areas. While they are NPhard for most settings, they are polynomial solvable for intervals. In this thesis, we consider the generalizations of hitting, covering and packing problems for intervals. We model these problems as mincost flow problems using nontrivial reduction and solve it using standard flow algorithms.
Demandhitting problem which is a generalization of hitting problem is defined as follows: Given N intervals, a positive integer demand for every interval, M points, a real weight for every point, select a subset of points H, such that every interval contains at least as many points in H as its demand and sum of weight of the points in H is minimized. Note that if the demand is one for all intervals, we get the standard hitting set problem. In this case, we give a dynamic programming based O(M + N) time algorithm assuming that intervals and points are sorted. A special case of the demandhitting set is the Khitting set problem where the demand of all the intervals is K. For the Khitting set problem, we give a O(M2N) time flow based algorithm. For the demandhitting problem, we make an assumption that no interval is contained in another interval. Under this assumption, we give a O(M2N) time flow based algorithm.
Demandcovering problem which is a generalization of covering problem is defined as follows: Given N intervals, a real weight for every interval, M points, a positive integer demand for every point, select a subset of intervals C, such that every point is contained in at least as many intervals in C as its demand and sum of weight of the intervals in C is minimized. Note that if the demand of points are one, we get the standard covering set problem. In this case, we give a dynamic programming based O(M + N log N) time algorithm assuming that points are sorted. A special case of the demandcovering set is the Kcovering set problem where the demand of all the points is K. For the Kcovering set problem, we give a O(MN2) time flow based algorithm. For the demandcovering problem, we give a O(MN2) time flow based algorithm.
Kpack points problem which is a generalization of packing problem is defined as follows: Given N intervals, an integer K, M points, a real weight for every point, select a subset of points Y , such that every interval contains at most K points from Y and sum of weight of the points in Y is maximized. Note that if K is one, we get the standard pack points problem. In this case, we give a dynamic programming based O(M + N) time algorithm assuming that points and intervals are sorted. For Kpack points problem, we give O(M2 log M) time flow based algorithm assuming that intervals and points are sorted.
Collections
Related items
Showing items related by title, author, creator and subject.

Some Theoretical Contributions To The Mutual Exclusion Problem
Alagarsamy, K (20121204) 
Solution Of Delayed Reinforcement Learning Problems Having Continuous Action Spaces
Ravindran, B (20120529) 
On A Cubic Sieve Congruence Related To The Discrete Logarithm Problem
Vivek, Srinivas V (20130521)There has been a rapid increase interest in computational number theory ever since the invention of publickey cryptography. Various attempts to solve the underlying hard problems behind publickey cryptosystems has led ...