Weighted geometric set multi-cover via quasi-uniform sampling

N. Bansal, K.R. Pruhs

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

20 Citations (Scopus)
2 Downloads (Pure)

Abstract

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
PublisherSpringer
Pages145-156
ISBN (Print)978-3-642-33089-6
DOIs
Publication statusPublished - 2012
Event20th Annual European Symposium on Algorithms (ESA 2012) - Ljubljana, Slovenia
Duration: 10 Sep 201212 Sep 2012
Conference number: 20
http://link.springer.com/book/10.1007/978-3-642-33090-2
http://www.informatik.uni-trier.de/~ley/db/conf/esa/esa2012.html

Publication series

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

Conference

Conference20th Annual European Symposium on Algorithms (ESA 2012)
Abbreviated titleESA 2012
CountrySlovenia
CityLjubljana
Period10/09/1212/09/12
Internet address

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

Cite this