@inproceedings{54560164e3254aae8e50c832e307b50b,
title = "On capacitated set cover problems",
abstract = "Recently, Chakrabarty et al. [5] initiated a systematic study of capacitated set cover problems, and considered the question of how their approximability relates to that of the uncapacitated problem on the same underlying set system. Here, we investigate this connection further and give several results, both positive and negative. In particular, we show that if the underlying set system satisfies a certain hereditary property, then the approximability of the capacitated problem is closely related to that of the uncapacitated version. We also give related lower bounds, and show that the hereditary property is necessary to obtain non-trivial results. Finally, we give some results for capacitated covering problems on set systems with low hereditary discrepancy and low VC dimension.",
author = "N. Bansal and R. Krishnaswamy and B. Saha",
year = "2011",
doi = "10.1007/978-3-642-22935-0\_4",
language = "English",
isbn = "978-3-642-22934-3",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "38--49",
editor = "L.A. Goldberg and K. Jansen and R. Ravi and J.D.P. Rolim",
booktitle = "Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings)",
address = "Germany",
}