Abstract
Given an instance of an optimization problem together with an optimal solution, we consider the scenario in which this instance is modified locally. In graph problems, e.g., a singular edge might be removed or added, or an edge weight might be varied, etc. For a problem U and such a local modification operation, let LM-U (local-modification-U) denote the resulting problem. The question is whether it is possible to exploit the additional knowledge of an optimal solution to the original instance or not, i.e., whether LM-U is computationally more tractable than U. Here, we give non-trivial examples both of problems where this is and problems where this is not the case. Our main results are these:
-
1.
The local modification to change the cost of a singular edge turns the traveling salesperson problem (TSP) into a problem LM-TSP which is as hard as TSP itself, i.e., unless P=NP, there is no polynomial-time p(n)-approximation algorithm for LM-TSP for any polynomial p. Moreover, LM-TSP where inputs must satisfy the β triangle inequality (LM-Δ β -TSP) remains NP-hard for all β > 1/2.
-
2.
For LM-Δ-TSP (i.e., metric LM-TSP), an efficient 1.4-approximation algorithm is presented. In other words, the additional information enables us to do better than if we simply used Christofides’ algorithm for the modified input.
-
3.
Similarly, for all 1 < β < 3.34899, we achieve a better approximation ratio for LM-Δ β -TSP than for Δ’-TSP.
-
4.
Metric TSP with deadlines (time windows), if a single deadline or the cost of a single edge is modified, exhibits the same lower bounds on the approximability in these local-modification versions as those currently known for the original problem. instance. A second construction inflates this advantage. Tours which start at time X, different from those that start between times X+g and X +ςg, may spend some extra time to visit a group of vertices which, unless visited early, will cause belated tours to run k times zigzag across a huge distance γ.
The following lemma describes the construction in detail. See Figure 5 for an overview.
This work was partially supported by SNF grant 200021-109252/1, by the research project GRID.IT, flmded by the Italian Ministry of Education, University and Research, and by the COST 293 (GRAAL) project funded by the European Union.
This author was staying at ETH Zurich when this work was done.
Please use the following format wheu citing this chapter: Böckenhauer, H.-J., Forlizzi, L., HromkoviS, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P., 2006, in International Federation for Information Processing, Volume 209, Fourth IFIP International Conference on Theoretical Computer Science-TCS 2006, eds. Navarro, G., Bertossi, L., Kohayakwa, Y., (Boston: Springer), pp. 251–270.
Chapter PDF
Similar content being viewed by others
References
T. Andreae: On the traveling salesman problem restricted to inputs satisfying a relaxed triangle inequality. Networks 38, 2001, pp. 59–67.
T. Andreae, H.-J. Bandelt: Performance guarantees for approximation algorithms depending on parameterized triangle inequalities. SIAM Journal on Discrete Mathematics 8, 1995, pp. 1–16.
M. Bender, C. Chekuri: Performance guarantees for TSP with a parameterized triangle inequality. Information Processing Letters 73, 2000, pp. 17–21.
H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, W. Unger: Approximation algorithms for TSP with sharpened triangle inequality. Information Processing Letters 75, 2000, pp. 133–138.
H.-J. Böckenhauer, J. Hromkovič, R. Klasing, S. Seibert, W. Unger: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theoretical Computer Science 285, 2002, pp. 3–24.
H.-J. Böckenhauer, J. Hromkovič, J. Kneis, J. Kupke: On the parameterized approximability of TSP with deadlines. Theory of Computing Systems, to appear.
H.-J. Böckenhauer, J. Hromkovič, J. Kneis, J. Kupke: On the approximation hardness of some generalizations of TSP. Proc. SWAT 2006, to appear.
H.-J. Böckenhauer, S. Seibert: Improved lower bounds on the approximability of the traveling salesman problem. RAIRO Theoretical Informatics and Applications 34, 2000, pp. 213–255.
N. Christofides: Worst-case analysis of a new heuristic for the travelling salesman problem. Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, 1976.
J.-F. Cordeau, G. Desaulniers, J. Desrosiers, M. M. Solomon, F. Soumis: VRP with time windows. In: P. Toth, D. Vigo (eds.): The Vehicle Routing Problem, SIAM 2001, pp. 157–193.
L. Forlizzi, J. Hromkovič, G. Proietti, S. Seibert: On the stability of approximation for Hamiltonian path problems. Algorithmic Operations Research 1(1), 2006, pp. 31–45.
H. Greenberg: An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization. In: D. L. Woodruff (ed.): Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, Kluwer Academic Publishers, 1998, pp. 97–148.
N. Guttmann-Beck, R. Hassin, S. Khuller, B. Raghavachari: Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28, 2000, pp. 422–437.
J. A. Hoogeveen: Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Operations Research Letters 10, 1978, pp. 178–193.
J. Hromkovič: Stability of approximation algorithms for hard optimization problems. Proc. SOFSEM’99, Springer LNCS 1725, 1999, pp. 29–47.
J. Hromkovič: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer 2003.
M. Libura: Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems. Discrete Applied Mathematics 30, 1991, pp. 197–211.
M. Libura, E. S. van der Poort, G. Sierksma, J. A. A. van der Veen: Stability aspects of the traveling salesman problem based on k-best solutions. Discrete Applied Mathematics 87, 1998, pp. 159–185.
Ch. Papadimitriou, K. Steiglitz: Some examples of difficult traveling salesman problems. Operations Research 26, 1978, pp. 434–443.
Y. N. Sotskov, V. K. Leontev, E. N. Gordeev: Some concepts of stability analysis in combinatorial optimization. Discrete Appl. Math. 58, 1995, pp. 169 190.
S. Van Hoesel, A. Wagelmans: On the complexity of postoptimality analysis of 0/1 programs. Discrete Applied Mathematics 91, 1999, pp. 251–263.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 International Federation for Information Processing
About this paper
Cite this paper
Böckenhauer, HJ. et al. (2006). Reusing Optimal TSP Solutions for Locally Modified Input Instances. In: Navarro, G., Bertossi, L., Kohayakawa, Y. (eds) Fourth IFIP International Conference on Theoretical Computer Science- TCS 2006. IFIP International Federation for Information Processing, vol 209. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-34735-6_21
Download citation
DOI: https://doi.org/10.1007/978-0-387-34735-6_21
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-34633-5
Online ISBN: 978-0-387-34735-6
eBook Packages: Computer ScienceComputer Science (R0)