Design of dynamic algorithms via primal-dual method

DOI10.1007/978-3-662-47672-7_17zbMATH Open1395.90210arXiv1604.05337OpenAlexW1017666284WikidataQ61609315 ScholiaQ61609315MaRDI QIDQ3448786FDOQ3448786

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)

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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
• Title not available (Why is that?)
• Simple Deterministic Algorithms for Fully Dynamic Maximal Matching
• Maintaining a large matching and a small vertex cover
• Deterministic Fully Dynamic Data Structures for Vertex Cover and Matching
• Fully Dynamic Maximal Matching in O (log n) Update Time

Cited In (7)

• Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover
• Title not available (Why is that?)
• Improved algorithm for dynamic b-Matching
• Approximating dynamic weighted vertex cover with soft capacities
• Title not available (Why is that?)
• 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)