Online and dynamic algorithms for set cover

DOI10.1145/3055399.3055493zbMath1370.90217arXiv1611.05646OpenAlexW2550458906MaRDI QIDQ4978000

Ravishankar Krishnaswamy, Anupam Gupta, Amit Kumar, Debmalya Panigrahi

Publication date: 17 August 2017

Published in: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

online algorithmscompetitive ratiodynamic algorithmsvertex covergraph matchingset coverhypergraph matchingrecourse

Mathematics Subject Classification ID

Hypergraphs (05C65) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Online algorithms; streaming algorithms (68W27)

Related Items (16)

Online load balancing with general reassignment cost ⋮ Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching ⋮ Deterministic dynamic matching in worst-case update time ⋮ Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Online hitting of unit balls and hypercubes in \(\mathbb{R}^d\) using points from \(\mathbb{Z}^d\) ⋮ Unnamed Item ⋮ Dynamic clustering to minimize the sum of radii ⋮ Permutation Strikes Back: The Power of Recourse in Online Metric Matching ⋮ Online packing of arbitrary sized items into designated and multipurpose bins ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Improved algorithm for dynamic b-Matching ⋮ Robust online algorithms for dynamic choosing problems

This page was built for publication: Online and dynamic algorithms for set cover