Show simple item record

dc.contributor.advisorGovindarajan, Satish
dc.contributor.authorDatta Krupa, R
dc.date.accessioned2018-05-29T07:20:57Z
dc.date.accessioned2018-07-31T04:40:22Z
dc.date.available2018-05-29T07:20:57Z
dc.date.available2018-07-31T04:40:22Z
dc.date.issued2018-05-29
dc.date.submitted2017
dc.identifier.urihttp://etd.iisc.ac.in/handle/2005/3628
dc.identifier.abstracthttp://etd.iisc.ac.in/static/etd/abstracts/4498/G28474-Abs.pdfen_US
dc.description.abstractInterval graphs are well studied structures. Intervals can represent resources like jobs to be sched-uled. Finding maximum independent set in interval graphs would correspond to scheduling maximum number of non-conflicting jobs on the computer. Most optimization problems on interval graphs like independent set, vertex cover, dominating set, maximum clique, etc can be solved efficiently using combinatorial algorithms in polynomial time. Hitting, Covering and Packing problems have been ex-tensively studied in the last few decades and have applications in diverse areas. While they are NP-hard for most settings, they are polynomial solvable for intervals. In this thesis, we consider the generaliza-tions of hitting, covering and packing problems for intervals. We model these problems as min-cost flow problems using non-trivial reduction and solve it using standard flow algorithms. Demand-hitting 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 demand-hitting set is the K-hitting set problem where the demand of all the intervals is K. For the K-hitting set problem, we give a O(M2N) time flow based algorithm. For the demand-hitting 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. Demand-covering 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 demand-covering set is the K-covering set problem where the demand of all the points is K. For the K-covering set problem, we give a O(MN2) time flow based algorithm. For the demand-covering problem, we give a O(MN2) time flow based algorithm. K-pack 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 pro-gramming based O(M + N) time algorithm assuming that points and intervals are sorted. For K-pack points problem, we give O(M2 log M) time flow based algorithm assuming that intervals and points are sorted.en_US
dc.language.isoen_USen_US
dc.relation.ispartofseriesG28474en_US
dc.subjectGeometric Hitting Problemen_US
dc.subjectGeometric Covering Problemen_US
dc.subjectGeometric Packing Problemen_US
dc.subjectHitting Seten_US
dc.subjectCovering Seten_US
dc.subjectPack Pointsen_US
dc.subjectInterval Graphsen_US
dc.subjectk-pack Pointsen_US
dc.subjectDemand-hitting Problemen_US
dc.subjectDemand-covering Problemen_US
dc.subject.classificationComputer Scienceen_US
dc.titleGeneralization of Hitting, Covering and Packing Problems on Intervalsen_US
dc.typeThesisen_US
dc.degree.nameMSc Enggen_US
dc.degree.levelMastersen_US
dc.degree.disciplineFaculty of Engineeringen_US


Files in this item

This item appears in the following Collection(s)

Show simple item record