Improved bounds for the online steiner tree problem in graphs of bounded edge-asymmetry
Spyros Angelopoulos · 2007
In this paper we consider the Online Steiner Tree problem in weighted directed graphs of bounded edge-asymmetry α. The edge-asymmetry of a directed graph is defined as the maximum ratio of the cost (weight) of antiparallel edges in the graph. The problem has applications in multicast routing over a network with non-symmetric links. We improve the previously known upper and lower bounds on the competitive ratio of any deterministic algorithm due to Faloutsos et al. In particular, we show that a better analysis of a simple greedy algorithm yields a competitive ratio of O (min {k, α log k/log log α}), where k denotes the number of terminals requested. On the negative side, we show a lower bound of Ω (min{k1-ε, α log k/log log k}) on the competitive ratio of every deterministic algorithm for the problem, for any arbitrarily small constant ε.