Dynamic set cover: improved algorithms and lower bounds
From MaRDI portal
Publication:5212753
DOI10.1145/3313276.3316376zbMath1433.68616arXiv1804.03197OpenAlexW2951922466MaRDI QIDQ5212753
Amir Abboud, Fabrizio Grandoni, Debmalya Panigrahi, Barna Saha, Raghavendra Addanki
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
Analysis of algorithms (68W40) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Randomized algorithms (68W20) Online algorithms; streaming algorithms (68W27)
Related Items
Deterministic dynamic matching in worst-case update time, Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover, Unnamed Item, Dynamic clustering to minimize the sum of radii