Weighted geometric set multi-cover via quasi-uniform sampling
<p>We give a randomized polynomial time algorithm with approximation ratio $O(\log \phi(n))$ for weighted set multi-cover instances with a shallow cell complexity of at most $f(z,k) =z\phi(z) k^{O(1)}$. Up to constant factors, this matches a recent result of Chan, Grant, Konemann and Sharpe fo...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Carleton University
2016-05-01
|
| Series: | Journal of Computational Geometry |
| Online Access: | http://jocg.org/index.php/jocg/article/view/126 |
| _version_ | 1818672038281216000 |
|---|---|
| author | Nikhil Bansal Kirk Pruhs |
| author_facet | Nikhil Bansal Kirk Pruhs |
| author_sort | Nikhil Bansal |
| collection | DOAJ |
| description | <p>We give a randomized polynomial time algorithm with approximation ratio $O(\log \phi(n))$ for weighted set multi-cover instances with a shallow cell complexity of at most $f(z,k) =z\phi(z) k^{O(1)}$. Up to constant factors, this matches a recent result of Chan, Grant, Konemann and Sharpe 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 $\mathbb{R}^3$. Another consequence is to show that the real diculty of many natural capacitated set covering problems lies with solving the associated priority cover problem only, and not with the associated multi-cover problem.</p> |
| first_indexed | 2024-12-17T07:33:32Z |
| format | Article |
| id | doaj.art-a3a530036b3342deb5f53faee2370437 |
| institution | Directory Open Access Journal |
| issn | 1920-180X |
| language | English |
| last_indexed | 2024-12-17T07:33:32Z |
| publishDate | 2016-05-01 |
| publisher | Carleton University |
| record_format | Article |
| series | Journal of Computational Geometry |
| spelling | doaj.art-a3a530036b3342deb5f53faee23704372022-12-21T21:58:24ZengCarleton UniversityJournal of Computational Geometry1920-180X2016-05-017110.20382/jocg.v7i1a1198Weighted geometric set multi-cover via quasi-uniform samplingNikhil BansalKirk Pruhs<p>We give a randomized polynomial time algorithm with approximation ratio $O(\log \phi(n))$ for weighted set multi-cover instances with a shallow cell complexity of at most $f(z,k) =z\phi(z) k^{O(1)}$. Up to constant factors, this matches a recent result of Chan, Grant, Konemann and Sharpe 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 $\mathbb{R}^3$. Another consequence is to show that the real diculty of many natural capacitated set covering problems lies with solving the associated priority cover problem only, and not with the associated multi-cover problem.</p>http://jocg.org/index.php/jocg/article/view/126 |
| spellingShingle | Nikhil Bansal Kirk Pruhs Weighted geometric set multi-cover via quasi-uniform sampling Journal of Computational Geometry |
| title | Weighted geometric set multi-cover via quasi-uniform sampling |
| title_full | Weighted geometric set multi-cover via quasi-uniform sampling |
| title_fullStr | Weighted geometric set multi-cover via quasi-uniform sampling |
| title_full_unstemmed | Weighted geometric set multi-cover via quasi-uniform sampling |
| title_short | Weighted geometric set multi-cover via quasi-uniform sampling |
| title_sort | weighted geometric set multi cover via quasi uniform sampling |
| url | http://jocg.org/index.php/jocg/article/view/126 |
| work_keys_str_mv | AT nikhilbansal weightedgeometricsetmulticoverviaquasiuniformsampling AT kirkpruhs weightedgeometricsetmulticoverviaquasiuniformsampling |