Design of Dynamic Algorithms via Primal-Dual Method

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(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(log 3 n) amortized update time, where n is the number of nodes in the graph.
Type de document :
Communication dans un congrès
ICALP 2018 - International Colloquium on Automata, Languages, and Programming, Jul 2015, Kyoto, Japan. 9134, pp.206-218, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-662-47672-7_17〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01964700
Contributeur : Marie-France Sagot <>
Soumis le : dimanche 23 décembre 2018 - 11:48:12
Dernière modification le : jeudi 7 février 2019 - 15:36:53

Fichier

bhattacharyaetal-1.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Sayan Bhattacharya, Monika Henzinger, Giuseppe Italiano. Design of Dynamic Algorithms via Primal-Dual Method. ICALP 2018 - International Colloquium on Automata, Languages, and Programming, Jul 2015, Kyoto, Japan. 9134, pp.206-218, 2015, Lecture Notes in Computer Science. 〈10.1007/978-3-662-47672-7_17〉. 〈hal-01964700〉

Partager

Métriques

Consultations de la notice

9

Téléchargements de fichiers

76