Design of dynamic algorithms via primal-dual method

Bhattacharya S, Henzinger M, Italiano GF. 2015. Design of dynamic algorithms via primal-dual method. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 206–218.

Download (ext.)
OA https://arxiv.org/abs/1604.05337 [Preprint]

DOI
10.1007/978-3-662-47672-7_17
Conference Paper | Published | English

Scopus indexed
Author
Bhattacharya, Sayan; Henzinger, MonikaISTA ; Italiano, Giuseppe F.
Series Title
LNCS
Abstract
In this paper, 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 𝑂(𝑓2)-approximately optimal solution in 𝑂(𝑓⋅log(π‘š+𝑛)) amortized update time, where 𝑓 is the maximum β€œfrequency” of an element, 𝑛 is the number of sets, and π‘š is the maximum number of elements in the universe at any point in time. (2) For the dynamic 𝑏-matching problem, we maintain an 𝑂(1)-approximately optimal solution in 𝑂(log3𝑛) amortized update time, where 𝑛 is the number of nodes in the graph.
Publishing Year
2015
Date Published
2015-01-01
Proceedings Title
42nd International Colloquium on Automata, Languages and Programming
Publisher
Springer Nature
Volume
9134
Page
206 - 218
Conference
ICALP: International Colloquium on Automata, Languages, and Programming
Conference Location
Kyoto, Japan
Conference Date
2015-07-06 – 2015-07-10
ISBN
9783662476710
ISSN
0302-9743
IST-REx-ID
11786

Cite this

Bhattacharya S, Henzinger M, Italiano GF. Design of dynamic algorithms via primal-dual method. In: 42nd International Colloquium on Automata, Languages and Programming. Vol 9134. Springer Nature; 2015:206-218. doi:10.1007/978-3-662-47672-7_17
Bhattacharya, S., Henzinger, M., & Italiano, G. F. (2015). Design of dynamic algorithms via primal-dual method. In 42nd International Colloquium on Automata, Languages and Programming (Vol. 9134, pp. 206–218). Kyoto, Japan: Springer Nature. https://doi.org/10.1007/978-3-662-47672-7_17
Bhattacharya, Sayan, Monika Henzinger, and Giuseppe F. Italiano. β€œDesign of Dynamic Algorithms via Primal-Dual Method.” In 42nd International Colloquium on Automata, Languages and Programming, 9134:206–18. Springer Nature, 2015. https://doi.org/10.1007/978-3-662-47672-7_17.
S. Bhattacharya, M. Henzinger, and G. F. Italiano, β€œDesign of dynamic algorithms via primal-dual method,” in 42nd International Colloquium on Automata, Languages and Programming, Kyoto, Japan, 2015, vol. 9134, pp. 206–218.
Bhattacharya S, Henzinger M, Italiano GF. 2015. Design of dynamic algorithms via primal-dual method. 42nd International Colloquium on Automata, Languages and Programming. ICALP: International Colloquium on Automata, Languages, and Programming, LNCS, vol. 9134, 206–218.
Bhattacharya, Sayan, et al. β€œDesign of Dynamic Algorithms via Primal-Dual Method.” 42nd International Colloquium on Automata, Languages and Programming, vol. 9134, Springer Nature, 2015, pp. 206–18, doi:10.1007/978-3-662-47672-7_17.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
URL
https://arxiv.org/abs/1604.05337
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Sources

arXiv 1604.05337

Search this title in

Google Scholar
ISBN Search