Spring 2018

Tight Bounds for Online Weighted Tree Augmentation

Monday, June 3rd, 2019 3:40 pm4:10 pm

Add to Calendar


David Williamson (Cornell University)

The Weighted Tree Augmentation problem (WTAP) is a fundamental problem in network design. In this talk, 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. We give a deterministic O(\log n)-competitive algorithm for online WTAP, which is tight up to constant factors. This is joint work with Seffi Naor and William Umboh.