Approximation hardness of deadline-TSP reoptimization
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. While positive examples are known e.g. for metric TSP, we give some negative examples here: 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. (C) 2009 Elsevier B.V. All rights reserved.
reoptimization tsp with deadlines approximation algorithms inapproximability