2015 | OriginalPaper | Buchkapitel
Optimal Competitiveness for the Rectilinear Steiner Arborescence Problem
verfasst von : Erez Kantor, Shay Kutten
Erschienen in: Automata, Languages, and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We present optimal online algorithms for two related known problems involving Steiner Arborescence, improving both the lower and the upper bounds. One of them is the well studied continuous problem of the
Rectilinear Steiner Arborescence
(
$$\text{RSA}$$
). We improve the lower bound and the upper bound on the competitive ratio for
$$\text{RSA}$$
from
$$O(\log N)$$
and
$$\varOmega (\sqrt{\log N})$$
to
$$\varTheta (\frac{\log N}{\log \log N})$$
, where
N
is the number of Steiner points. This separates the competitive ratios of
$$\text{RSA}$$
and the Symetric-
$$\text{RSA}$$
$$(\text{SRSA})$$
, two problems for which the bounds of Berman and Coulston is STOC 1997 were identical. The second problem is one of the Multimedia Content Distribution problems presented by Papadimitriou et al. in several papers and Charikar et al. SODA 1998. It can be viewed as the discrete counterparts (or a network counterpart) of
$$\text{RSA}$$
. For this second problem we present tight bounds also in terms of the network size, in addition to presenting tight bounds in terms of the number of Steiner points (the latter are similar to those we derived for
$$\text{RSA}$$
).