An Improved Analysis of Greedy for Online Steiner Forest

This paper considers the classic Online Steiner Forest problem where one is given a (weighted) graph G and an arbitrary set of k terminal pairs s1, t1, . . . , s k , t k that are required to be connected. The goal is to maintain a minimum-weight sub-graph that satisfies all the connectivity requirements as the pairs are revealed one by one. It has been known for a long time that no algorithm (even randomized) can be better than Ω(log(k))-competitive for this problem. Interestingly, a simple greedy algorithm is already very efficient for this problem. This algorithm can be informally described as follows:

Upon arrival of a new pair si, ti, connect si and ti with the shortest path in the current metric, contract the metric along the chosen path and wait for the next pair.

Although simple and intuitive, greedy proved itself challenging to analyze and its competitive ratio is a longstanding open problem in the area of online algorithms. The last progress on this problem is due to an elegant analysis by Awerbuch, Azar, and Bartal [SODA 1996], who showed that greedy is O(log 2 (k))-competitive.

In this paper, we identify a natural measure of the "efficiency" of greedy that we call the contraction. The contraction of a pair si, ti is the ratio between the distance dG(si, ti) in the graph G and the actual cost that greedy pays for connecting the pair si, ti. Intuitively, a worst-case instance should be an instance on which greedy is very "inefficient", i.e. an instance for which all pairs have a relatively small contraction. Indeed, one can remark that all hard instances that appeared in the literature are such that all pairs have a contraction of exactly 1 (which is the smallest contraction possible). Our main result, among others, is to show that greedy is O(log(k) log log(k))-competitive on such instances.

At the heart of this new result lies an original use of dual fitting, in which we use the dual solution not only to lower bound the optimum as it is usually the case in competitive analysis, but also to recursively partition the global instance into several disjoint instances of much smaller complexity.