License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.88
URN: urn:nbn:de:0030-drops-106647
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10664/
Naor, Joseph (Seffi) ;
Umboh, Seeun William ;
Williamson, David P.
Tight Bounds for Online Weighted Tree Augmentation
Abstract
The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this paper, we consider this problem in the online setting. We are given an n-vertex spanning tree T and an additional set L of edges (called links) with costs. Then, terminal pairs arrive one-by-one and our task is to maintain a low-cost subset of links F such that every terminal pair that has arrived so far is 2-edge-connected in T cup F. This online problem was first studied by Gupta, Krishnaswamy and Ravi (SICOMP 2012) who used it as a subroutine for the online survivable network design problem. They gave a deterministic O(log^2 n)-competitive algorithm and showed an Omega(log n) lower bound on the competitive ratio of randomized algorithms. The case when T is a path is also interesting: it is exactly the online interval set cover problem, which also captures as a special case the parking permit problem studied by Meyerson (FOCS 2005). The contribution of this paper is to give tight results for online weighted tree and path augmentation problems. The main result of this work is a deterministic O(log n)-competitive algorithm for online WTAP, which is tight up to constant factors.
BibTeX - Entry
@InProceedings{naor_et_al:LIPIcs:2019:10664,
author = {Joseph (Seffi) Naor and Seeun William Umboh and David P. Williamson},
title = {{Tight Bounds for Online Weighted Tree Augmentation}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {88:1--88:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10664},
URN = {urn:nbn:de:0030-drops-106647},
doi = {10.4230/LIPIcs.ICALP.2019.88},
annote = {Keywords: Online algorithms, competitive analysis, tree augmentation, network design}
}
|
Keywords: |
|
Online algorithms, competitive analysis, tree augmentation, network design |
|
Collection: |
|
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.07.2019 |
