Journal
INFORMATION AND COMPUTATION
Volume 261, Issue -, Pages 219-239Publisher
ACADEMIC PRESS INC ELSEVIER SCIENCE
DOI: 10.1016/j.ic.2018.02.005
Keywords
Dynamic algorithms; Primal-dual method; Data structures
Funding
- European Research Council under the European Union/ERC [340506]
- EU [317532]
- MIUR (the Italian Ministry of Education, University and Research)
Ask authors/readers for more resources
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(f center dot log(m + n)) amortized update time, where fis the maximum frequency of an element, nis the number of sets, and mis 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(log3n) amortized update time, where nis the number of nodes in the graph. (C) 2018 Elsevier Inc. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available