N&O seminar: William Umboh (University of Sydney)

Everyone is welcome to attend the N&O seminar of William Umboh with the title 'Tight Bounds for Online Weighted Tree Augmentation'.
  • What Networks & Optimization English Seminars
  • When 26-07-2019 from 14:00 to 15:00 (Europe/Amsterdam / UTC200)
  • Where Room L016 at CWI, Science Park 123 in Amsterdam
  • Contact Name Daniel Dadush
  • Web Visit external website
  • Add event to calendar iCal

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.