Tight Bounds for Online Weighted Tree Augmentation. 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 nvertex spanning tree T and an additional set L of edges (called links) with costs. Then, terminal pairs arrive onebyone and our task is to maintain a lowcost subset of links F such that every terminal pair that has arrived so far is 2edgeconnected 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(log2 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.

Reliable Hubs for PartiallyDynamic AllPairs Shortest Paths in Directed Graphs We give new partiallydynamic algorithms for the allpairs shortest paths problem in weighted directed graphs. Most importantly, we give a new deterministic incremental algorithm for the problem that handles updates in widetildeO(mn43logWepsilon) total time (where the edge weights are from 1,W) and explicitly maintains a (1epsilon)approximate distance matrix. For a fixed epsilonu003e0, this is the first deterministic partially dynamic algorithm for allpairs shortest paths in directed graphs, whose update time is o(n2) regardless of the number of edges. Furthermore, we also show how to improve the stateoftheart partially dynamic randomized algorithms for allpairs shortest paths Baswana et al. STOCu002702, Bernstein STOCu002713 from Monte Carlo randomized to Las Vegas randomized without increasing the running time bounds (with respect to the widetildeO(cdot) notation).  :121,results are obtained by giving new algorithms for the problem of dynamically maintaining hubs, that is a set of widetildeO(nd) vertices which hit a shortest path between each pair of vertices, provided it has hoplength Omega(d). We give new subquadratic deterministic and Las Vegas algorithms for maintenance of hubs under either edge insertions or deletions.