Everyone is welcome to attend the N&O seminar of William Umboh with the title 'Tight Bounds for Online Weighted Tree Augmentation'.
Abstract: 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 the union of T and 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 David Williamson.
