Online network design algorithms via hierarchical decompositions

DOI10.1137/1.9781611973730.91zbMATH Open1372.68312arXiv1410.4240OpenAlexW2949813243MaRDI QIDQ5363006FDOQ5363006

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)

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.

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

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

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)

Cited In (14)

• Tight bounds for online weighted tree augmentation
• On the Facility Location Problem in Online and Dynamic Models.
• Online constrained forest and prize-collecting network design
• A randomized \(O(\log n)\)-competitive algorithm for the online connected facility location problem
• Title not available (Why is that?)
• Designing Networks with Good Equilibria under Uncertainty
• Dynamic Balanced Graph Partitioning
• Title not available (Why is that?)
• Online network design with outliers
• Group parking permit problems
• Online and approximate network construction from bounded connectivity constraints
• On generalizations of the parking permit problem and network leasing problems
• Tight Bounds for Online Weighted Tree Augmentation
• 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)