The power of amortized recourse for online graph problems
From MaRDI portal
Publication:6176555
DOI10.1007/978-3-031-18367-6_7arXiv2206.01077OpenAlexW4313020478MaRDI QIDQ6176555
Hsiang-Hsuan Liu, Jonathan Toole-Charignon
Publication date: 25 July 2023
Published in: Approximation and Online Algorithms (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2206.01077
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Ramsey numbers and an approximation algorithm for the vertex cover problem
- Online maximum matching with recourse
- Approximating maximum independent sets by excluding subgraphs
- A primal-dual online deterministic algorithm for matching with delays
- Online constrained optimization with recourse
- Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
- A better approximation ratio for the vertex cover problem
- Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs
- Two-sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm
- The Power of Deferral: Maintaining a Constant-Competitive Steiner Tree Online
- Fully-Dynamic Bin Packing with Little Repacking
- 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS)
- Tight Bounds for Online Coloring of Basic Graph Classes
- Online Bipartite Matching with Amortized O (log 2 n ) Replacements
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- The Power of Recourse for Online MST and TSP
- Relaxing the irrevocability requirement for online graph algorithms
- Online Domination: The Value of Getting to Know All Your Neighbors.
