Dynamic algorithms via the primal-dual method

DOI10.1016/j.ic.2018.02.005zbMath1395.90209OpenAlexW2792298309MaRDI QIDQ1640995

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

Publication date: 14 June 2018

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ic.2018.02.005

zbMATH Keywords

primal-dual methoddata structuresdynamic algorithms

Mathematics Subject Classification ID

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

Related Items

Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ A discrete dynamics approach to sparse calculation and applied in ontology science

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Maintaining a large matching and a small vertex cover
• A threshold of ln n for approximating set 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
• A General Approximation Technique for Constrained Forest Problems
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b–Matching Problems in Nonbipartite Graphs
• Fully Dynamic Maximal Matching in O (log n) Update Time