Solving Structured Set Cover Instances via Geometric Sampling
|Affiliation:||University of Waterloo|
|Room:||Mathematics & Computer Building (MC) 5158|
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
200 University Avenue West
Waterloo, ON N2L 3G1