Design of dynamic algorithms via primal-dual method

DOI10.1007/978-3-662-47672-7_17MaRDI QIDQ3448786zbMATH OpenOpenAlexWikidataFDO

Authors Sayan Bhattacharya, Giuseppe F. Italiano, 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)

Abstract: We develop a dynamic version of the primal-dual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an $O(f^2)$-approximately optimal solution in $O(fcdotlog(m+n))$ amortized update time, where $f$ is the maximum "frequency" of an element, $n$ is the number of sets, and $m$ is the maximum number of elements in the universe at any point in time. (2) For the dynamic $b$-matching problem, we maintain an $O(1)$-approximately optimal solution in $O(lo{g}^{3}n)$ amortized update time, where $n$ is the number of nodes in the graph.

Recommendations

• Dynamic algorithms via the primal-dual method
• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Online and dynamic algorithms for set cover
• The Design of Competitive Online Algorithms via a Primal—Dual Approach
• Dynamic set cover: improved algorithms and lower bounds

Cites work

• scientific article; zbMATH DE number 3121287 (Why is no real title available?)
• scientific article; zbMATH DE number 3231692 (Why is no real title available?)
• A linear-time approximation algorithm for the weighted vertex cover problem
• 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
• Maintaining a large matching and a small vertex cover
• The Design of Competitive Online Algorithms via a Primal—Dual Approach

Cited in

(8)

• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Dynamic clustering to minimize the sum of radii
• Dynamic algorithms via the primal-dual method
• An \(o(1)\)-approximation algorithm for dynamic weighted vertex cover with soft capacity
• Approximating dynamic weighted vertex cover with soft capacities
• Improved algorithm for dynamic \(b\)-matching
• Dynamic clustering to minimize the sum of radii
• Deterministic dynamic matching in \(O(1)\) update time

This page was built for publication: Design of dynamic algorithms via primal-dual method

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