Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2004), Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem, Theoretical Computer Science, 310, 1-3, p. 135-146. http://dx.doi.org/10.1016/S0304-3975(03)00376-1
Type
Article accepté pour publication ou publiéDate
2004Journal name
Theoretical Computer ScienceVolume
310Number
1-3Publisher
Elsevier
Pages
135-146
Publication identifier
Metadata
Show full item recordAbstract (EN)
Local search has been widely used in combinatorial optimization (Local Search in Combinatorial Optimization, Wiley, New York, 1997), however, in the case of multicriteria optimization almost no results are known concerning the ability of local search algorithms to generate “good” solutions with performance guarantee. In this paper, we introduce such an approach for the classical traveling salesman problem (TSP) problem (Proc. STOC’00, 2000, pp. 126–133). We show that it is possible to get in linear time, a Image -approximate Pareto curve using an original local search procedure based on the 2-opt neighborhood, for the bicriteria TSP(1,2) problem where every edge is associated to a couple of distances which are either 1 or 2 (Math. Oper. Res. 18 (1) (1993) 1).Subjects / Keywords
Local search; Multicriteria TSP; Approximation algorithmsRelated items
Showing items related by title and author.
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2003) Communication / Conférence
-
Monnot, Jérôme; Gourvès, Laurent; Bampis, Evripidis; Angel, Eric (2005) Communication / Conférence
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2003) Communication / Conférence
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2014) Chapitre d'ouvrage
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2007) Document de travail / Working paper