The Steiner tree reoptimization problem with sharpened triangle inequality

• In this paper, we deal with several reoptimization variants of the Steiner tree problem in graphs obeying a sharpened β -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+ γ for an arbitrary small γ > 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 + β )-approximation algorithms, and even polynomialtime approximation schemes, whereas for metric graphs ( β = 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 β -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 β < 1/2 + ln(3)/4 ≈ 0. 775.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences (hsv//eng)

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)

NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

Steiner tree problem

hardness

reoptimization

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)