On the Hardness of Reoptimization with Multiple Given Solutions

• Autorzy: Böckenhauer H. J. , Hromkovič J. , Sprock A.
• Języki publikacji: EN

Abstrakty

EN

In reoptimization, we consider the following scenario: Given an instance of a hard optimization problem together with an optimal solution for it, we want to solve a locally modified instance of the problem. It has recently been shown for several hard optimization problems that their corresponding reoptimization variants remain NP-hard or even hard to approximate whereas they often admit improved approximation ratios. In this paper, we investigate a generalization of the reoptimization concept where we are given not only one optimal solution but multiple optimal solutions for an instance. We prove, for some variants of the Steiner tree problem and the traveling salesman problem, that the known reoptimization hardness results carry over to this generalized setting. Moreover, we consider the performance of local search strategies on reoptimization problems. We show that local search does notwork for solving TSP reoptimization, even in the presence ofmultiple solutions.

Słowa kluczowe

EN

reoptimization; Steiner tree; TSP; multiple given solution; hardness

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 110, nr 1-4
• Strony: 59--76
• Opis fizyczny: Bibliogr. 22 poz., wykr.

Twórcy

autor

Böckenhauer H. J.

autor

Hromkovič J.

autor

Sprock A.

• Department of Computer Science, ETH Zurich, Switzerland,

Bibliografia

• [1] Archetti, C., Bertazzi, L., Speranza, M. G.: Reoptimizing the traveling salesman problem, Networks, 42(3), 2003, 154-159.
• [2] Archetti, C., Bertazzi, L., Speranza, M. G.: Reoptimizing the 0-1 Knapsack Problem, Technical Report 267, University of Brescia, 2006.
• [3] Ausiello, G., Bonifaci, V., Escoffier, B.: Complexity and Approximation in Reoptimization, Computability in Context: Computation and Logic in the Real World (A. S. B. Cooper, Ed.), Imperial College Press/World Scientific, 2010, To appear.
• [4] Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation, Springer-Verlag, Berlin, 1999, ISBN 3-540-65431-3.
• [5] Ausiello, G., Escoffier, B., Monnot, J., Paschos, V. T.: Reoptimization of minimum and maximum traveling salesman's tours, Proc. of the 10th Scandinavian Workshop on Algorithm Theory (SWAT 2006) (L. Arge, R. V. Freivalds, Eds.), 4059, Springer-Verlag, Berlin, 2006, ISBN 3-540-35753-X.
• [6] Berg, T., Hempel, H.: Reoptimization of Traveling Salesperson Problems: Changing Single Edge-Weights, Proc. of the 3rd International Conference on Language and Automata Theory and Applications (LATA 2009) (A. H. Dediu, A.-M. Ionescu, C.Mart´ın-Vide, Eds.), 5457, Springer-Verlag, 2009, ISBN 978-3-642-00981-5.
• [7] Biló, D., Böckenhauer, H.-J., Hromkovič, J., Královič, R., Mömke, T., Widmayer, P., Zych, A.: Reoptimization of Steiner trees, Proc. of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008) (J. Gudmundsson, Ed.), 5124, Springer-Verlag, 2008, ISBN 978-3-540-69900-2.
• [8] Biló, D., Zych, A.: New Reoptimization Techniques employed to Steiner Tree Problem, Proceedings of the 6th Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 11), 2011, To appear.
• [9] 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), Proc. of the 4th IFIP International Conference on Theoretical Computer Science (TCS 2006) (G. Navarro, L. E. Bertossi, Y. Kohayakawa, Eds.), 209, Springer-Verlag, New York, 2006, ISBN 0-387-34633-3.
• [10] 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), 2007, 83-93.
• [11] Böckenhauer, H.-J., Freiermuth, K., Hromkovič, J., Mömke, T., Sprock, A., Steffen, B.: Steiner tree reoptimization in graphs with sharpened triangle inequality, Journal of Discrete Algorithms, 2011, To appear.
• [12] Böckenhauer, H.-J., Hromkovič, J., Královič, R., Mömke, T., Rossmanith, P.: Reoptimization of Steiner Trees: Changing the Terminal Set, Theoretical Computer Science, 410(36), 2009, 3428-3435, ISSN 0304-3975.
• [13] Böckenhauer, H.-J., Hromkovič, J., Mömke, T., Widmayer, P.: On the Hardness of Reoptimization, Proc. Of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008) (V. Geffert, J. Karhumäki, A. Bertoni, B. Preneel, P. Návrat,M. Bieliková, Eds.), 4910, Springer-Verlag, Berlin, 2008, ISBN 978-3-540-77565-2.
• [14] Böckenhauer, H.-J., Hromkovič, J., Sprock, A.: Knowing all optimal solutions does not help for TSP reoptimization, Models of Computation, Cooperation and Life, 2011, To appear.
• [15] Böckenhauer, H.-J., Komm, D.: Reoptimization of the Metric Deadline TSP, Proc. of the 33th International SymposiumonMathematical Foundations of Computer Science (MFCS 2008) (E. Ochmanski, J. Tyszkiewicz, Eds.), 5162, Springer-Verlag, 2008, ISBN 978-3-540-85237-7.
• [16] Cayley, A.: A Theorem on Trees, Quart. J. Math. 23, 1889.
• [17] 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, 1976.
• [18] Escoffier, B., Milanič, M., Paschos, V. T.: Simple and fast reoptimizations for the Steiner tree problem, Algorithmic Operations Research, 4(2), 2009, 86-94.
• [19] Freiermuth, K., Stewénius, H.: Multi-dimensional diamond graph constructions, 2009, Unpublished manuscript.
• [20] Hromkovič, J.: Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, Texts in Theoretical Computer Science. An EATCS Series, Springer-Verlag, Berlin, 2003.
• [21] Papadimitriou, C. H., Steiglitz, K.: Some examples of difficult traveling salesman problems, Operations Research, 26, 1978, 434-443.
• [22] Schäffter,M. W.: Scheduling with Forbidden Sets, Discrete Applied Mathematics, 72(1-2), 1997, 155-166.