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 language | English |
|---|---|
| Title of host publication | Algorithms – ESA 2012 (20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings) |
| Editors | L. Epstein, P. Ferragina |
| Place of Publication | Berlin |
| Publisher | Springer |
| Pages | 145-156 |
| ISBN (Print) | 978-3-642-33089-6 |
| DOIs | |
| Publication status | Published - 2012 |
| Event | 20th Annual European Symposium on Algorithms (ESA 2012) - Ljubljana, Slovenia Duration: 10 Sept 2012 → 12 Sept 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
| Name | Lecture Notes in Computer Science |
|---|---|
| Volume | 7501 |
| ISSN (Print) | 0302-9743 |
Conference
| Conference | 20th Annual European Symposium on Algorithms (ESA 2012) |
|---|---|
| Abbreviated title | ESA 2012 |
| Country/Territory | Slovenia |
| City | Ljubljana |
| Period | 10/09/12 → 12/09/12 |
| Internet address |