Dynamic set cover: improved algorithms and lower bounds

DOI10.1145/3313276.3316376MaRDI QIDQ5212753zbMATH OpenOpenAlexFDO

Authors Amir Abboud, Raghavendra Addanki, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha

Publication date 30 January 2020

Published in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1804.03197

zbMATH Keywords

competitive ratiodynamic algorithmonline algorithmrandomized algorithmset cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Approximation algorithms (68W25) Online algorithms; streaming algorithms (68W27) Analysis of algorithms (68W40) Combinatorial optimization (90C27)

Abstract: We give new upper and lower bounds for the {em dynamic} set cover problem. First, we give a $(1+epsilon)f$-approximation for fully dynamic set cover in $O(f^{2}logn/epsilo{n}^5)$ (amortized) update time, for any $epsilon>0$, where $f$ is the maximum number of sets that an element belongs to. In the decremental setting, the update time can be improved to $O(f^2/epsilo{n}^5)$, while still obtaining an $(1+epsilon)f$-approximation. These are the first algorithms that obtain an approximation factor linear in $f$ for dynamic set cover, thereby almost matching the best bounds known in the offline setting and improving upon the previous best approximation of $O(f^2)$ in the dynamic setting. To complement our upper bounds, we also show that a linear dependence of the update time on $f$ is necessary unless we can tolerate much worse approximation factors. Using the recent distributed PCP-framework, we show that any dynamic set cover algorithm that has an amortized update time of $O(f^{1-epsilon})$ must have an approximation factor that is $Omega(n^{d}elta)$ for some constant $delta>0$ under the Strong Exponential Time Hypothesis.

Recommendations

• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Online and dynamic algorithms for set cover
• Dynamic algorithms via the primal-dual method
• Deterministically maintaining a (2 + )-approximate minimum vertex cover in O(1/^2) amortized update time
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time

Cited in

(14)

• Dynamic algorithms via the primal-dual method
• Dynamic clustering to minimize the sum of radii
• Design of dynamic algorithms via primal-dual method
• Online and dynamic algorithms for set cover
• More dynamic data structures for geometric set cover with sublinear update time
• scientific article; zbMATH DE number 7651158 (Why is no real title available?)
• Deterministic dynamic matching in worst-case update time
• Fully Dynamic Set Cover via Hypergraph Maximal Matching: An Optimal Approximation Through a Local Approach.
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Dynamic \(((1+\epsilon)\ln n)\)-approximation algorithms for minimum set cover and dominating set
• Dynamic geometric set cover, revisited
• Dynamic geometric set cover, revisited
• The complexity of non-stationary reinforcement learning
• Dynamic programming based algorithms for set multicover and multiset multicover problems

This page was built for publication: Dynamic set cover: improved algorithms and lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5212753)