\input zb-basic
\input zb-ioport
\iteman{io-port 06033181}
\itemau{B\"ockenhauer, Hans-Joachim; Freiermuth, Karin; Hromkovi\v{c}, Juraj; M\"omke, Tobias; Sprock, Andreas; Steffen, Bj\"orn}
\itemti{Steiner tree reoptimization in graphs with sharpened triangle inequality.}
\itemso{J. Discrete Algorithms 11, 73-86 (2012).}
\itemab
Summary: We deal with several reoptimization variants of the Steiner tree problem in graphs obeying a sharpened $\beta $-triangle inequality. A reoptimization algorithm exploits the knowledge of an optimal solution to a problem instance for finding good solutions for a locally modified instance. We show that, in graphs satisfying a sharpened triangle inequality (and even in graphs where edge-costs are restricted to the values 1 and $1+\gamma $ for an arbitrary small $\gamma >0$), Steiner tree reoptimization still is NP-hard for several different types of local modifications, and even APX-hard for some of them. As for the upper bounds, for some local modifications, we design linear-time $(1/2+\beta )$-approximation algorithms, and even polynomial-time approximation schemes, whereas for metric graphs $(\beta =1)$, none of these reoptimization variants is known to permit a PTAS. As a building block for some of these algorithms, we employ a $2\beta $-approximation algorithm for the classical Steiner tree problem on such instances, which might be of independent interest since it improves over the previously best known ratio for any $\beta <1/2+\ln(3)/4 \approx 0.775$.
\itemrv{~}
\itemcc{}
\itemut{Steiner tree; reoptimization; approximation algorithms; approximability; sharpened triangle inequality}
\itemli{doi:10.1016/j.jda.2011.03.014}
\end