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) 
Batch Processsor Scheduling  A Class Of Problems In Steel Casting Foundries
Ramasubramaniam, M (20100915)Modern manufacturing systems need new types of scheduling methods. While traditional scheduling methods are primarily concerned with sequencing of jobs, modern manufacturing environments provide the additional possibility ... 
Schemes for Smooth Discretization And Inverse Problems  Case Study on Recovery of Tsunami Source Parameters
Devaraj, G (20171017)This thesis deals with smooth discretization schemes and inverse problems, the former used in efficient yet accurate numerical solutions to forward models required in turn to solve inverse problems. The aims of the thesis ...