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.

Study of Diverse Chemical Problems by NMR and the Design of Novel Two Dimensional Techniques
Mishra, Sandeep Kumar (20180518)The research work reported in this thesis is focused on the chiral analysis, quantification of enantiomeric composition, assignment of absolute configuration of molecules with chosen functional groups. The weak intramolecular ... 
Multimodal Deep Learning for MultiLabel Classification and Ranking Problems
Dubey, Abhishek (20180611)In recent years, deep neural network models have shown to outperform many state of the art algorithms. The reason for this is, unsupervised pretraining with multilayered deep neural networks have shown to learn better ... 
Algorithmic and Combinatorial Questions on Some Geometric Problems on Graphs
Babu, Jasine (20180508)This thesis mainly focuses on algorithmic and combinatorial questions related to some geometric problems on graphs. In the last part of this thesis, a graph coloring problem is also discussed. Boxicity and Cubicity: These ...