TY - GEN

T1 - Weighted capacitated, priority, and geometric set cover via improved quasi-uniform sampling

AU - Chan, Timothy M.

AU - Grant, Elyot

AU - Könemann, Jochen

AU - Sharpe, Malcolm

N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.

PY - 2012

Y1 - 2012

N2 - 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. We also show how to derandomize our algorithm. Our main result has several immediate consequences. Among them, we settle an open question of Chakrabarty et al. [8] by showing that weighted instances of the capacitated covering problem with underlying network structure have O(1)-approximations. Additionally, our improvements to Varadarajan's sampling framework yield several new results for weighted geometric set cover, hitting set, and dominating set problems. In particular, for weighted covering problems exhibiting linear (or near-linear) union complexity, we obtain approximability results agreeing with those known for the unweighted case. For example, we obtain a constant approximation for the weighted disk cover problem, improving upon the 2O(log* n)-approximation known prior to our work and matching the O(1)-approximation known for the unweighted variant.

AB - 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. We also show how to derandomize our algorithm. Our main result has several immediate consequences. Among them, we settle an open question of Chakrabarty et al. [8] by showing that weighted instances of the capacitated covering problem with underlying network structure have O(1)-approximations. Additionally, our improvements to Varadarajan's sampling framework yield several new results for weighted geometric set cover, hitting set, and dominating set problems. In particular, for weighted covering problems exhibiting linear (or near-linear) union complexity, we obtain approximability results agreeing with those known for the unweighted case. For example, we obtain a constant approximation for the weighted disk cover problem, improving upon the 2O(log* n)-approximation known prior to our work and matching the O(1)-approximation known for the unweighted variant.

UR - http://www.scopus.com/inward/record.url?scp=84860151583&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84860151583&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973099.125

DO - 10.1137/1.9781611973099.125

M3 - Conference contribution

AN - SCOPUS:84860151583

SN - 9781611972108

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1576

EP - 1585

BT - Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

PB - Association for Computing Machinery

T2 - 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2012

Y2 - 17 January 2012 through 19 January 2012

ER -