The Steiner tree reoptimization problem with sharpened triangle inequality
| Autor: | Juraj Hromkovic, Tobias Mömke, Björn Steffen, Andreas Sprock, Hans-Joachim Böckenhauer, Karin Freiermuth |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2010 |
| Předmět: |
STEINER SYSTEMS (COMBINATORICS)
Sharpened triangle inequality Steiner tree problem Reoptimization TREES (GRAPH THEORY) PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS STEINER-SYSTEME (KOMBINATORIK) Approximation PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME BÄUME (GRAPHENTHEORIE) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Combinatorics symbols.namesake Data processing computer science 0202 electrical engineering electronic engineering information engineering Mathematics Block (data storage) Discrete mathematics Triangle inequality 010201 computation theory & mathematics Metric (mathematics) symbols 020201 artificial intelligence & image processing ddc:004 MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783642130724 CIAC Technical Report / ETH Zurich, Department of Computer Science, 658 |
| DOI: | 10.3929/ethz-a-006837610 |
| Popis: | 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 lineartime (1/2+β)-approximation algorithms, and even polynomial-time 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. Technical Report / ETH Zurich, Department of Computer Science, 658 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|