Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866914420318273536 |
|---|---|
| author | Mitrović, Slobodan Ramachandran, Srikkanth Rubinfeld, Ronitt Singhal, Mihir |
| author_facet | Mitrović, Slobodan Ramachandran, Srikkanth Rubinfeld, Ronitt Singhal, Mihir |
| contents | In this work, we focus on designing an efficient Local Computation Algorithm (LCA) for the set cover problem, which is a core optimization task.
The state-of-the-art LCA for computing $O(\log Δ)$-approximate set cover, developed by Grunau, Mitrović, Rubinfeld, and Vakilian [SODA '20], achieves query complexity of $Δ^{O(\log Δ)} \cdot f^{O(\log Δ\cdot (\log \log Δ+ \log \log f))}$, where $Δ$ is the maximum set size, and $f$ is the maximum frequency of any element in sets.
We present a new LCA that solves this problem using $f^{O(\log Δ)}$ queries.
Specifically, for instances where $f = \text{poly} \log Δ$, our algorithm improves the query complexity from $Δ^{O(\log Δ)}$ to $Δ^{O(\log \log Δ)}$.
Our central technical contribution in designing LCAs is to aggressively sparsify the input instance but to allow for \emph{retroactive updates}.
Namely, our main LCA sometimes ``corrects'' decisions it made in the previous recursive LCA calls.
It enables us to achieve stronger concentration guarantees, which in turn allows for more efficient and ``sparser'' LCA execution.
We believe that this technique will be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_23715 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates Mitrović, Slobodan Ramachandran, Srikkanth Rubinfeld, Ronitt Singhal, Mihir Data Structures and Algorithms In this work, we focus on designing an efficient Local Computation Algorithm (LCA) for the set cover problem, which is a core optimization task. The state-of-the-art LCA for computing $O(\log Δ)$-approximate set cover, developed by Grunau, Mitrović, Rubinfeld, and Vakilian [SODA '20], achieves query complexity of $Δ^{O(\log Δ)} \cdot f^{O(\log Δ\cdot (\log \log Δ+ \log \log f))}$, where $Δ$ is the maximum set size, and $f$ is the maximum frequency of any element in sets. We present a new LCA that solves this problem using $f^{O(\log Δ)}$ queries. Specifically, for instances where $f = \text{poly} \log Δ$, our algorithm improves the query complexity from $Δ^{O(\log Δ)}$ to $Δ^{O(\log \log Δ)}$. Our central technical contribution in designing LCAs is to aggressively sparsify the input instance but to allow for \emph{retroactive updates}. Namely, our main LCA sometimes ``corrects'' decisions it made in the previous recursive LCA calls. It enables us to achieve stronger concentration guarantees, which in turn allows for more efficient and ``sparser'' LCA execution. We believe that this technique will be of independent interest. |
| title | Improved Local Computation Algorithms for Greedy Set Cover via Retroactive Updates |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2603.23715 |