Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929561471549440 |
|---|---|
| author | Bukov, Anton Solomon, Shay Zhang, Tianyi |
| author_facet | Bukov, Anton Solomon, Shay Zhang, Tianyi |
| contents | The dynamic set cover problem has been subject to extensive research since the pioneering works of [Bhattacharya et al, 2015] and [Gupta et al, 2017]. The input is a set system $(U, S)$ on a fixed collection $S$ of sets and a dynamic universe of elements, where each element appears in a most $f$ sets and the cost of each set lies in the range $[1/C, 1]$, and the goal is to efficiently maintain an approximately-minimum set cover under insertions and deletions of elements.
Most previous work considers the low-frequency regime, namely $f = O(\log n)$, and this line of work has culminated with a deterministic $(1+ε)f$-approximation algorithm with amortized update time $O(\frac{f^2}{ε^3} + \frac{f}{ε^2}\log C)$ [Bhattacharya et al, 2021]. In the high-frequency regime of $f = Ω(\log n)$, an $O(\log n)$-approximation algorithm with amortized update time $O(f\log n)$ was given by [Gupta et al, 2017].
Interestingly, at the intersection of the two regimes, i.e., $f = Θ(\log n)$, the state-of-the-art results coincide: approximation $Θ(f) = Θ(\log n)$ with amortized update time $O(f^2) = O(f \log n) = O(\log^2 n)$. Up to this date, no previous work achieved update time of $o(f^2)$.
In this paper we break the $Ω(f^2)$ update time barrier via the following results: (1) $(1+ε)f$-approximation can be maintained in $O\left(\frac{f}{ε^3}\log^*f + \frac{f}{ε^3}\log C\right) = O_{ε,C}(f \log^* f)$ expected amortized update time; our algorithm works against an adaptive adversary. (2) $(1+ε)f$-approximation can be maintained deterministically in $O\left(\frac{1}εf\log f + \frac{f}{ε^3} + \frac{f\log C}{ε^2}\right) = O_{ε,C}(f \log f)$ amortized update time. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_00793 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier Bukov, Anton Solomon, Shay Zhang, Tianyi Data Structures and Algorithms The dynamic set cover problem has been subject to extensive research since the pioneering works of [Bhattacharya et al, 2015] and [Gupta et al, 2017]. The input is a set system $(U, S)$ on a fixed collection $S$ of sets and a dynamic universe of elements, where each element appears in a most $f$ sets and the cost of each set lies in the range $[1/C, 1]$, and the goal is to efficiently maintain an approximately-minimum set cover under insertions and deletions of elements. Most previous work considers the low-frequency regime, namely $f = O(\log n)$, and this line of work has culminated with a deterministic $(1+ε)f$-approximation algorithm with amortized update time $O(\frac{f^2}{ε^3} + \frac{f}{ε^2}\log C)$ [Bhattacharya et al, 2021]. In the high-frequency regime of $f = Ω(\log n)$, an $O(\log n)$-approximation algorithm with amortized update time $O(f\log n)$ was given by [Gupta et al, 2017]. Interestingly, at the intersection of the two regimes, i.e., $f = Θ(\log n)$, the state-of-the-art results coincide: approximation $Θ(f) = Θ(\log n)$ with amortized update time $O(f^2) = O(f \log n) = O(\log^2 n)$. Up to this date, no previous work achieved update time of $o(f^2)$. In this paper we break the $Ω(f^2)$ update time barrier via the following results: (1) $(1+ε)f$-approximation can be maintained in $O\left(\frac{f}{ε^3}\log^*f + \frac{f}{ε^3}\log C\right) = O_{ε,C}(f \log^* f)$ expected amortized update time; our algorithm works against an adaptive adversary. (2) $(1+ε)f$-approximation can be maintained deterministically in $O\left(\frac{1}εf\log f + \frac{f}{ε^3} + \frac{f\log C}{ε^2}\right) = O_{ε,C}(f \log f)$ amortized update time. |
| title | Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2308.00793 |