In this paper, we develop a dynamic version of the primaldual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O(f2)-approximately optimal solution in O(f · log(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(log3 n) amortized update time, where n is the number of nodes in the graph.
Bhattacharya, S., Henzinger, M., Italiano, G.f. (2015). Design of dynamic algorithms via primal-dual method. In Proceedings Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015 (pp.206-218). Springer Verlag [10.1007/978-3-662-47672-7_17].
Design of dynamic algorithms via primal-dual method
ITALIANO, GIUSEPPE FRANCESCO
2015-01-01
Abstract
In this paper, we develop a dynamic version of the primaldual method for optimization problems, and apply it to obtain the following results. (1) For the dynamic set-cover problem, we maintain an O(f2)-approximately optimal solution in O(f · log(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(log3 n) amortized update time, where n is the number of nodes in the graph.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
