Random Order Set Cover is as Easy as Offline
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916314241564672 |
|---|---|
| author | Gupta, Anupam Kehne, Gregory Levin, Roie |
| author_facet | Gupta, Anupam Kehne, Gregory Levin, Roie |
| contents | We give a polynomial-time algorithm for OnlineSetCover with a competitive ratio of $O(\log mn)$ when the elements are revealed in random order, essentially matching the best possible offline bound of $O(\log n)$ and circumventing the $Ω(\log m \log n)$ lower bound known in adversarial order. We also extend the result to solving pure covering IPs when constraints arrive in random order.
The algorithm is a multiplicative-weights-based round-and-solve approach we call LearnOrCover. We maintain a coarse fractional solution that is neither feasible nor monotone increasing, but can nevertheless be rounded online to achieve the claimed guarantee (in the random order model). This gives a new offline algorithm for SetCover that performs a single pass through the elements, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_06842 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | Random Order Set Cover is as Easy as Offline Gupta, Anupam Kehne, Gregory Levin, Roie Data Structures and Algorithms We give a polynomial-time algorithm for OnlineSetCover with a competitive ratio of $O(\log mn)$ when the elements are revealed in random order, essentially matching the best possible offline bound of $O(\log n)$ and circumventing the $Ω(\log m \log n)$ lower bound known in adversarial order. We also extend the result to solving pure covering IPs when constraints arrive in random order. The algorithm is a multiplicative-weights-based round-and-solve approach we call LearnOrCover. We maintain a coarse fractional solution that is neither feasible nor monotone increasing, but can nevertheless be rounded online to achieve the claimed guarantee (in the random order model). This gives a new offline algorithm for SetCover that performs a single pass through the elements, which may be of independent interest. |
| title | Random Order Set Cover is as Easy as Offline |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2111.06842 |