Weighted geometric set multi-cover via quasi-uniform sampling

N. Bansal, K.R. Pruhs

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

26 Citations (Scopus)
2 Downloads (Pure)


We give a randomized polynomial time algorithm with approximation ratio O(logf(n)) for weighted set multi-cover instances with a shallow cell complexity of at most f(n,k)¿=¿n f(n) k O(1). Up to constant factors, this matches a recent result of Könemann et al. for the set cover case, i.e. when all the covering requirements are 1. One consequence of this is an O(1)-approximation for geometric weighted set multi-cover problems when the geometric objects have linear union complexity; for example when the objects are disks, unit cubes or halfspaces in R3. Another consequence is to show that the real difficulty of many natural capacitated set covering problems lies with solving the associated priority cover problem only, and not with the associated multi-cover problem.
Original languageEnglish
Title of host publicationAlgorithms – ESA 2012 (20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings)
EditorsL. Epstein, P. Ferragina
Place of PublicationBerlin
ISBN (Print)978-3-642-33089-6
Publication statusPublished - 2012
Event20th Annual European Symposium on Algorithms (ESA 2012) - Ljubljana, Slovenia
Duration: 10 Sept 201212 Sept 2012
Conference number: 20

Publication series

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


Conference20th Annual European Symposium on Algorithms (ESA 2012)
Abbreviated titleESA 2012
Internet address


Dive into the research topics of 'Weighted geometric set multi-cover via quasi-uniform sampling'. Together they form a unique fingerprint.

Cite this