On capacitated set cover problems

N. Bansal, R. Krishnaswamy, B. Saha

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

9 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationApproximation, 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)
EditorsL.A. Goldberg, K. Jansen, R. Ravi, J.D.P. Rolim
Place of PublicationBerlin
PublisherSpringer
Pages38-49
ISBN (Print)978-3-642-22934-3
DOIs
Publication statusPublished - 2011

Publication series

NameLecture Notes in Computer Science
Volume6845
ISSN (Print)0302-9743

Fingerprint

Dive into the research topics of 'On capacitated set cover problems'. Together they form a unique fingerprint.

Cite this