The Library
Design of dynamic algorithms via primal-dual method
Tools
Bhattacharya, Sayan, Henzinger, Monika and Italiano, Giuseppe F. (2015) Design of dynamic algorithms via primal-dual method. In: International Colloquium on Automata, Languages, and Programming, Kyoto, Japan, 6-10 Jul 2015. Published in: Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, 9134 pp. 206-218. ISBN 9783662476710. doi:10.1007/978-3-662-47672-7_17 ISSN 0302-9743.
|
PDF
WRAP-design-dynamic-algorithms-via-primal-dual-Bhattacharya-2015.pdf - Accepted Version - Requires a PDF viewer. Download (681Kb) | Preview |
Official URL: http://dx.doi.org/10.1007/978-3-662-47672-7_17
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 O(f2)O(f2) -approximately optimal solution in O(f⋅log(m+n))O(f⋅log(m+n)) amortized update time, where ff is the maximum “frequency” of an element, nn is the number of sets, and mm is the maximum number of elements in the universe at any point in time. (2) For the dynamic bb -matching problem, we maintain an O(1)O(1) -approximately optimal solution in O(log3n)O(log3n) amortized update time, where nn is the number of nodes in the graph.
Item Type: | Conference Item (Paper) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
Library of Congress Subject Headings (LCSH): | Algorithms, Combinatorial optimization | ||||
Series Name: | Lecture Notes in Computer Science | ||||
Journal or Publication Title: | Automata, Languages, and Programming : 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II | ||||
Publisher: | Springer Verlag | ||||
Place of Publication: | Berlin, Heidelberg | ||||
ISBN: | 9783662476710 | ||||
ISSN: | 0302-9743 | ||||
Book Title: | Automata, Languages, and Programming | ||||
Editor: | Halldórsson , M. and Iwama , K. and Kobayashi , N. and Speckmann , B. | ||||
Official Date: | 2015 | ||||
Dates: |
|
||||
Volume: | 9134 | ||||
Page Range: | pp. 206-218 | ||||
DOI: | 10.1007/978-3-662-47672-7_17 | ||||
Status: | Peer Reviewed | ||||
Publication Status: | Published | ||||
Access rights to Published version: | Restricted or Subscription Access | ||||
Date of first compliant deposit: | 26 September 2017 | ||||
Date of first compliant Open Access: | 26 September 2017 | ||||
Conference Paper Type: | Paper | ||||
Title of Event: | International Colloquium on Automata, Languages, and Programming | ||||
Type of Event: | Conference | ||||
Location of Event: | Kyoto, Japan | ||||
Date(s) of Event: | 6-10 Jul 2015 |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year