Abstract
We consider the following reoptimization scenario: Given an instance of an optimization problem together with an optimal solution, we want to find a high-quality solution for a locally modified instance. The naturally arising question is whether the knowledge of an optimal solution to the unaltered instance can help in solving the locally modified instance. In this paper, we survey some partial answers to this questions: Using some variants of the traveling salesman problem and the Steiner tree problem as examples, we show that the answer to this question depends on the considered problem and the type of local modification and can be totally different: For instance, for some reoptimization variant of the metric TSP, we get a 1.4-approximation improving on the best known approximation ratio of 1.5 for the classical metric TSP. For the Steiner tree problem on graphs with bounded cost function, which is APX-hard in its classical formulation, we even obtain a PTAS for the reoptimization variant. On the other hand, for a variant of TSP, where some vertices have to be visited before a prescribed deadline, we are able to show that the reoptimization problem is exactly as hard to approximate as the original problem.
This work was partially supported by SBF grant C 06.0108 as part of the COST 293 (GRAAL) project funded by the European Union.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Archetti, C., Bertazzi, L., Speranza, M.G.: Reoptimizing the traveling salesman problem. Networks 42, 154–159 (2003)
Ausiello, G., Escoffier, B., Monnot, J., Paschos, V.Th.: Reoptimization of minimum and maximum traveling salesman’s tours. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 196–207. Springer, Heidelberg (2006)
Bern, M.W., Plassmann, P.E.: The Steiner problem with edge lengths 1 and 2. Information Processing Letters 32(4), 171–176 (1989)
Böckenhauer, H.-J., Forlizzi, L., Hromkovič, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: Reusing optimal TSP solutions for locally modified input instances (extended abstract). In: IFIP TCS 2006. Proc. of the 4th IFIP International Conference on Theoretical Computer Science, pp. 251–270. Springer, Norwell (2006)
Böckenhauer, H.-J., Forlizzi, L., Hromkovič, J., Kneis, J., Kupke, J., Proietti, G., Widmayer, P.: On the approximability of TSP on local modifications of optimally solved instances. Algorithmic Operations Research 2(2), 83–93 (2007)
Böckenhauer, H.-J., Hromkovič, J., Klasing, R., Seibert, S., Unger, W.: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem (extended abstract). In: Bongiovanni, G., Petreschi, R., Gambosi, G. (eds.) CIAC 2000. LNCS, vol. 1767, pp. 72–86. Springer, Heidelberg (2000)
Böckenhauer, H.-J., Hromkovič, J., Klasing, R., Seibert, S., Unger, W.: Approximation algorithms for TSP with sharpened triangle inequality. Information Processing Letters 75, 133–138 (2000)
Böckenhauer, H.-J., Hromkovič, J., Klasing, R., Seibert, S., Unger, W.: An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality (extended abstract). In: Reichel, H., Tison, S. (eds.) STACS 2000. LNCS, vol. 1770, pp. 382–394. Springer, Heidelberg (2000)
Böckenhauer, H.-J., Hromkovič, J., Klasing, R., Seibert, S., Unger, W.: Towards the notion of stability of approximation for hard optimization tasks and the traveling salesman problem. Theoretical Computer Science 285, 3–24 (2002)
Böckenhauer, H.-J., Hromkovič, J., Kneis, J., Kupke, J.: On the parameterized approximability of TSP with deadlines. Theory of Computing Systems (to appear)
Böckenhauer, H.-J., Hromkovič, J., Kneis, J., Kupke, J.: On the approximation hardness of some generalizations of TSP. In: Arge, L., Freivalds, R. (eds.) SWAT 2006. LNCS, vol. 4059, pp. 184–195. Springer, Heidelberg (2006)
Böckenhauer, H.-J., Hromkovič, J., Královič, R., Mömke, T., Rossmanith, P.: Reoptimization of Steiner trees: changing the terminal set (submitted)
Böckenhauer, H.-J., Seibert, S.: Improved lower bounds on the approximability of the traveling salesman problem. RAIRO Theoretical Informatics and Applications 34, 213–255 (2000)
Christofides, N.: 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)
Cordeau, J.-F., Desaulniers, G., Desrosiers, J., Solomon, M.M., Soumis, F.: VRP with time windows. In: Toth, P., Vigo, D. (eds.) The Vehicle Routing Problem, SIAM 2001, pp. 157–193 (2001)
Dreyfus, S.E., Wagner, R.A.: The Steiner problem in graphs. Networks 1, 195–207 (1971/72)
Forlizzi, L., Hromkovič, J., Proietti, G., Seibert, S.: On the stability of approximation for Hamiltonian path problems. Algorithmic Operations Research 1(1), 31–45 (2006)
Garey, M., Johnson, D.: Computers and Intractability. W. H. Freeman and Co., New York (1979)
Greenberg, H.: An annotated bibliography for post-solution analysis in mixed integer and combinatorial optimization. In: Woodruff, D.L. (ed.) Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, pp. 97–148. Kluwer Academic Publishers, Dordrecht (1998)
Goldreich, O.: Bravely, moderately - A common theme in four recent works. In: SIGACT News, vol. 37, pp. 31–46. ACM, New York (2006)
Guttmann-Beck, N., Hassin, R., Khuller, S., Raghavachari, B.: Approximation algorithms with bounded performance guarantees for the clustered traveling salesman problem. Algorithmica 28, 422–437 (2000)
Hoogeveen, J.A.: Analysis of Christofides’ heuristic: Some paths are more difficult than cycles. Operations Research Letters 10, 178–193 (1978)
Hromkovič, J.: Stability of approximation algorithms for hard optimization problems. In: Bartosek, M., Tel, G., Pavelka, J. (eds.) SOFSEM 1999. LNCS, vol. 1725, pp. 29–47. Springer, Heidelberg (1999)
Hromkovič, J.: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer, Heidelberg (2003)
Libura, M.: Sensitivity analysis for minimum Hamiltonian path and traveling salesman problems. Discrete Applied Mathematics 30, 197–211 (1991)
Libura, M., van der Poort, E.S., Sierksma, G., van der Veen, J.A.A.: Stability aspects of the traveling salesman problem based on k-best solutions. Discrete Applied Mathematics 87, 159–185 (1998)
Mölle, D., Richter, S., Rossmanith, P.: A faster algorithm for the Steiner tree problem. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 561–570. Springer, Heidelberg (2006)
Prömel, H.J., Steger, A.: The Steiner Tree Problem. Friedr. Vieweg & Sohn, Braunschweig (2002)
Papadimitriou, Ch., Steiglitz, K.: Some examples of difficult traveling salesman problems. Operations Research 26, 434–443 (1978)
Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proc. of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 770–779. ACM, New York (2000)
Sotskov, Y.N., Leontev, V.K., Gordeev, E.N.: Some concepts of stability analysis in combinatorial optimization. Discrete Appl. Math. 58, 169–190 (1995)
Van Hoesel, S., Wagelmans, A.: On the complexity of postoptimality analysis of 0/1 programs. Discrete Applied Mathematics 91, 251–263 (1999)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Böckenhauer, HJ., Hromkovič, J., Mömke, T., Widmayer, P. (2008). On the Hardness of Reoptimization. In: Geffert, V., Karhumäki, J., Bertoni, A., Preneel, B., Návrat, P., Bieliková, M. (eds) SOFSEM 2008: Theory and Practice of Computer Science. SOFSEM 2008. Lecture Notes in Computer Science, vol 4910. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77566-9_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-77566-9_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-77565-2
Online ISBN: 978-3-540-77566-9
eBook Packages: Computer ScienceComputer Science (R0)