Solving Structured Set Cover Instances via Geometric Sampling
| Speaker: | Jochen Koenemann |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
The minimum-weight set cover problem is widely known to be O(log n)-approximable, with no improvement possible in the general case. We take the approach of exploiting problem structure to achieve better results, by providing a geometry-inspired algorithm whose approximation guarantee depends solely on an instance-specific combinatorial property known as shallow cell complexity (SCC). Roughly speaking, a set cover instance has low SCC if any column-induced submatrix of the corresponding element-set incidence matrix has few distinct rows. By adapting and improving Varadarajan's recent quasi-uniform random sampling method for weighted geometric covering problems, we obtain strong approximation algorithms for a structurally rich class of weighted covering problems with low SCC.
Joint work with T. Chan, E. Grant and M. Sharpe