Résumés
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 LM-U (local-modification-U) denote the same problem as U, but in 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, i.e., how to devise better algorithms for LM-U than for U. Note that this need not be possible in all cases: The general problem of LM-TSP 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 > 12 . However, for LM- -TSP (i.e., metric LM-TSP), we will present an efficient 1.4-approximation 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 < < 3.34899, we achieve a better approximation ratio for LM- -TSP than for -TSP. For 12 ≤ < 1, we show how to obtain an approximation ratio arbitrarily close to 1, for sufficiently large input graphs.
Keywords:
- TSP,
- approximation algorithms,
- local modifications,
- relaxed triangle inequality,
- sharpened triangle inequality
Veuillez télécharger l’article en PDF pour le lire.
Télécharger