dc.contributor.advisor Govindarajan, Satish dc.contributor.author Datta Krupa, R dc.date.accessioned 2018-05-29T07:20:57Z dc.date.accessioned 2018-07-31T04:40:22Z dc.date.available 2018-05-29T07:20:57Z dc.date.available 2018-07-31T04:40:22Z dc.date.issued 2018-05-29 dc.date.submitted 2017 dc.identifier.uri http://etd.iisc.ac.in/handle/2005/3628 dc.identifier.abstract http://etd.iisc.ac.in/static/etd/abstracts/4498/G28474-Abs.pdf en_US dc.description.abstract Interval 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 eﬃciently 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.iso en_US en_US dc.relation.ispartofseries G28474 en_US dc.subject Geometric Hitting Problem en_US dc.subject Geometric Covering Problem en_US dc.subject Geometric Packing Problem en_US dc.subject Hitting Set en_US dc.subject Covering Set en_US dc.subject Pack Points en_US dc.subject Interval Graphs en_US dc.subject k-pack Points en_US dc.subject Demand-hitting Problem en_US dc.subject Demand-covering Problem en_US dc.subject.classification Computer Science en_US dc.title Generalization of Hitting, Covering and Packing Problems on Intervals en_US dc.type Thesis en_US dc.degree.name MSc Engg en_US dc.degree.level Masters en_US dc.degree.discipline Faculty of Engineering en_US
﻿