Dynamic algorithms via the primal-dual method

DOI10.1016/J.IC.2018.02.005MaRDI QIDQ1640995zbMATH OpenOpenAlexFDO

Authors 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

data structuresdynamic algorithmsprimal-dual method

Mathematics Subject Classification ID

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

Recommendations

• Design of dynamic algorithms via primal-dual method
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Online and dynamic algorithms for set cover
• Dynamic set cover: improved algorithms and lower bounds
• Deterministic fully dynamic approximate vertex cover and fractional matching in \(O(1)\) amortized update time

Cites work

• A General Approximation Technique for Constrained Forest Problems
• A linear-time approximation algorithm for the weighted vertex cover problem
• A threshold of ln n for approximating set cover
• Approximation algorithms for combinatorial problems
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Deterministic fully dynamic data structures for vertex cover and matching
• Fully Dynamic Maximal Matching in O (log n) Update Time
• scientific article; zbMATH DE number 3121287 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• Maintaining a large matching and a small vertex cover
• Near Linear Time Approximation Schemes for Uncapacitated and Capacitated b–Matching Problems in Nonbipartite Graphs
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)

Cited in

(6)

• Design of dynamic algorithms via primal-dual method
• Online and dynamic algorithms for set cover
• A discrete dynamics approach to sparse calculation and applied in ontology science
• Dynamic set cover: improved algorithms and lower bounds
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Fully dynamic sequential and distributed algorithms for MAX-CUT

This page was built for publication: Dynamic algorithms via the primal-dual method

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1640995)