Optimal Competitiveness for Symmetric Rectilinear Steiner Arborescence and Related Problems

Abstract

We present optimal competitive algorithms for two interrelated known problems involving Steiner Arborescence. One is the continuous problem of the Symmetric Rectilinear Steiner Arborescence (${\sc SRSA}$), whose online version was studied by Berman and Coulston as a symmetric version of the known Rectilinear Steiner Arborescence (RSA) problem. A very related, but discrete problem (studied separately in the past) is the online Multimedia Content Delivery (${\sc MCD}$) problem on line networks, presented originally by Papadimitriou, Ramanathan, and Rangan. An efficient content delivery was modeled as a low cost Steiner arborescence in a grid of network×time they defined. We study here the version studied by Charikar, Halperin, and Motwani (who used the same problem definitions, but removed some constraints on the inputs). The bounds on the competitive ratios introduced separately in the above papers were similar for the two problems: O(logN) for the continuous problem and O(logn) for the network problem, where N was the number of terminals to serve, and n was the size of the network. The lower bounds were $\Omega(\sqrt{\log N})$ and $\Omega(\sqrt{\log n})$ correspondingly.

Berman and Coulston conjectured that both the upper bound and the lower bound could be improved. We disprove this conjecture and close these quadratic gaps for both problems. We present deterministic algorithms that are competitive optimal: $O(\sqrt{\log N})$ for ${\sc SRSA}$ and $O(\min \{\sqrt{\log n},\sqrt{\log N} \})$ for ${\sc MCD}$, matching the lower bounds for these two online problems. We also present a $\Omega(\sqrt[3]{\log n})$ lower bound on the competitiveness of any randomized algorithm that solves the online MCD problem.