Online network design algorithms via hierarchical decompositions

DOI10.1137/1.9781611973730.91MaRDI QIDQ5363006zbMATH OpenOpenAlexFDO

Authors Seeun William Umboh

Publication date 5 October 2017

Published in Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.4240

Mathematics Subject Classification ID

Online algorithms; streaming algorithms (68W27) Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Abstract: We develop a new approach for online network design and obtain improved competitive ratios for several problems. Our approach gives natural deterministic algorithms and simple analyses. At the heart of our work is a novel application of embeddings into hierarchically well-separated trees (HSTs) to the analysis of online network design algorithms --- we charge the cost of the algorithm to the cost of the optimal solution on any HST embedding of the terminals. This analysis technique is widely applicable to many problems and gives a unified framework for online network design. In a sense, our work brings together two of the main approaches to online network design. The first uses greedy-like algorithms and analyzes them using dual-fitting. The second uses tree embeddings and results in randomized $O(logn)$-competitive algorithms, where $n$ is the total number of vertices in the graph. Our approach uses deterministic greedy-like algorithms but analyzes them via HST embeddings of the terminals. Our proofs are simpler as we do not need to carefully construct dual solutions and we get $O(logk)$ competitive ratios, where $k$ is the number of terminals. In this paper, we apply our approach to obtain deterministic $O(logk)$-competitive online algorithms for the following problems. - Steiner network with edge duplication. Previously, only a randomized $O(logn)$-competitive algorithm was known. - Rent-or-buy. Previously, only deterministic $O(lo{g}^{2}k)$-competitive and randomized $O(logk)$-competitive algorithms by Awerbuch, Azar and Bartal (2004) were known. - Connected facility location. Previously, only a randomized $O(lo{g}^{2}k)$-competitive algorithm by San Felice, Williamson and Lee (2014) was known. - Prize-collecting Steiner forest. We match the competitive ratio first achieved by Qian and Williamson (2011) and give a simpler analysis.

Recommendations

• scientific article; zbMATH DE number 6469194
• A general approach to online network optimization problems
• Online and stochastic survivable network design
• Online and Stochastic Survivable Network Design
• Near-optimal online algorithms for prize-collecting Steiner problems

Cited in

(19)

• Tight bounds for online weighted tree augmentation
• Tight bounds for online weighted tree augmentation
• Online constrained forest and prize-collecting network design
• On the Facility Location Problem in Online and Dynamic Models.
• Online degree-bounded Steiner network design
• A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
• Online and stochastic survivable network design
• Online network design with outliers
• Online network design with outliers
• scientific article; zbMATH DE number 6469194 (Why is no real title available?)
• LAST but not least: online spanners for buy-at-bulk
• Group parking permit problems
• A deterministic algorithm for online Steiner tree leasing
• Online and approximate network construction from bounded connectivity constraints
• Online facility location with deletions
• On generalizations of the parking permit problem and network leasing problems
• Dynamic balanced graph partitioning
• Designing networks with good equilibria under uncertainty
• Adversarial bandits with knapsacks

This page was built for publication: Online network design algorithms via hierarchical decompositions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363006)