Given an instance of TSP together with an optimal solution, we consider the scenario in which this instance is modified locally, where a local modification consists in the alteration of the weight of a single edge. More generally, for a problem $U$, let $\textsc{lm-}U$ (local-modification-$U$) denote the same problem as~$U$, but in $\textsc{lm-}U$, we are also given an optimal solution to an instance from which the input instance can be derived by a local modification. The question is how to exploit this additional knowledge, \ie how to devise better algorithms for $\textsc{lm-}U$ than for~$U$. Note that this need not be possible in all cases: The general problem of \tweakTSP is as hard as \TSP itself, \ie unless $P=NP$, there is no polynomial-time $p(n)$-approximation algorithm for \tweakTSP for any polynomial~$p$. Moreover, \tweakTSP where inputs must satisfy the $\beta$-triangle inequality (\tweakTSPDB) remains NP-hard for all $\beta>\frac{1}{2}$. However, for \tweakTSPD (\ie metric \tweakTSP), we will present an efficient $1.4$-approx\-i\-ma\-tion algorithm. In other words, the additional information enables us to do better than if we simply used Christofides' algorithm for the modified input. Similarly, for all $1<\beta<3.34899$, we achieve a better approximation ratio for \tweakTSPDB than for \TSPDB. For $\frac{1}{2}\leq\beta<1$, we show how to obtain an approximation ratio arbitrarily close to~$1$, for sufficiently large input graphs.

### On the Approximability of TSP on Local Modifications of Optimally Solved Instances

#### Abstract

Given an instance of TSP together with an optimal solution, we consider the scenario in which this instance is modified locally, where a local modification consists in the alteration of the weight of a single edge. More generally, for a problem $U$, let $\textsc{lm-}U$ (local-modification-$U$) denote the same problem as~$U$, but in $\textsc{lm-}U$, we are also given an optimal solution to an instance from which the input instance can be derived by a local modification. The question is how to exploit this additional knowledge, \ie how to devise better algorithms for $\textsc{lm-}U$ than for~$U$. Note that this need not be possible in all cases: The general problem of \tweakTSP is as hard as \TSP itself, \ie unless $P=NP$, there is no polynomial-time $p(n)$-approximation algorithm for \tweakTSP for any polynomial~$p$. Moreover, \tweakTSP where inputs must satisfy the $\beta$-triangle inequality (\tweakTSPDB) remains NP-hard for all $\beta>\frac{1}{2}$. However, for \tweakTSPD (\ie metric \tweakTSP), we will present an efficient $1.4$-approx\-i\-ma\-tion algorithm. In other words, the additional information enables us to do better than if we simply used Christofides' algorithm for the modified input. Similarly, for all $1<\beta<3.34899$, we achieve a better approximation ratio for \tweakTSPDB than for \TSPDB. For $\frac{1}{2}\leq\beta<1$, we show how to obtain an approximation ratio arbitrarily close to~$1$, for sufficiently large input graphs.
##### Scheda breve Scheda completa Scheda completa (DC)
2007
File in questo prodotto:
Non ci sono file associati a questo prodotto.
##### Pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11697/4903
• ND
• ND
• ND