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 γ.