05912174

a

05912174 B\"ockenhauer, Hans-Joachim Hromkovi\v{c}, Juraj Sprock, Andreas Knowing all optimal solutions does not help for TSP reoptimization. Kelemen, Jozef (ed.) et al., Computation, cooperation, and life. Essays dedicated to Gheorghe P\u{a}un on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-642-19999-8/pbk). Lecture Notes in Computer Science 6610, 7-15 (2011). 2011 Berlin: Springer EN reoptimization TSP inapproximability

doi:10.1007/978-3-642-20000-7_2

Summary: The concept of reoptimization models the following question: Given an instance of an optimization problem together with an optimal solution, does this knowledge help for finding a high-quality solution for a locally modified instance? We briefly survey the known results about reoptimization and consider a generalization of the model where not only one optimal solution is given, but the set of all optimal solutions for an instance is available for free. We use the traveling salesman problem as an example to prove that there exist problems for which this additional knowledge does not help at all for improving the approximability.