|
|
Discrete Mathematics and Optimization Seminar
|
Oct. 5th, 2009
|
Two generalizations of (0,1)-covering problems
Deeparnab Chakrabarty
University of Waterloo
|
Pick your favorite (set) covering problem: for the purpose of this talk consider the line-cover problem of covering a set of points on a line by line segments. We call a covering problem (0,1) if any set covers any element at most once. This terminology arises from casting this problem as a covering integer program (CIP) where the constraint matrix is {0,1}.
The second problem, which we call the priority covering problem, is another (0,1) covering problem obtained as follows. We say a set covers an element iff it contains it and the supply of the set is larger than the demand of the element. Given this new set system, we want to choose a standard set cover, the minimum cost family of sets which covers every element at least once.
We are interested in connecting the approximability, and in particular the integrality gaps of the corresponding CIPs, of these generalized problems to that of the original (0,1) problem. In this talk, we will describe some partial progress we've made. In particular, we show that for the line cover problem the integrality gaps of both are within a constant factor of the original one's.
Joint work with Elyot Grant and Jochen Konemann
|
|
|
|