Design of Dynamic Algorithms via Primal-Dual Method

DOI10.1007/978-3-662-47672-7_17zbMath1395.90210arXiv1604.05337OpenAlexW1017666284WikidataQ61609315 ScholiaQ61609315MaRDI QIDQ3448786

Giuseppe F. Italiano, Sayan Bhattacharya, Monika R. Henzinger

Publication date: 27 October 2015

Published in: Automata, Languages, and Programming (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Combinatorial optimization (90C27) Data structures (68P05)

Related Items (7)

Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Unnamed Item ⋮ Dynamic clustering to minimize the sum of radii ⋮ Unnamed Item ⋮ Deterministic dynamic matching in \(O(1)\) update time ⋮ Approximating dynamic weighted vertex cover with soft capacities ⋮ Improved algorithm for dynamic b-Matching

Cites Work

• Unnamed Item
• Unnamed Item
• Maintaining a large matching and a small vertex cover
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• A linear-time approximation algorithm for the weighted vertex cover problem
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• Fully Dynamic Maximal Matching in O (log n) Update Time

This page was built for publication: Design of Dynamic Algorithms via Primal-Dual Method