Approximating the Pareto Curve with Local Search for the Bicriteria TSP (1, 2) Problem (extended abstract)
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2003), Approximating the Pareto Curve with Local Search for the Bicriteria TSP (1, 2) Problem (extended abstract), in Lingas, Andrzej; Nilsson, Bengt J., Fundamentals of Computation Theory 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings, Springer : Berlin, p. 39-48. http://dx.doi.org/10.1007/978-3-540-45077-1_5
Type
Communication / ConférenceDate
2003Conference title
14th International Symposium on Fundamentals of Computation Theory (FCT 2003)Conference date
2003-08Conference city
MalmöConference country
SuèdeBook title
Fundamentals of Computation Theory 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, ProceedingsBook author
Lingas, Andrzej; Nilsson, Bengt J.Publisher
Springer
Series title
Lecture Notes in Computer ScienceSeries number
2751Published in
Berlin
ISBN
978-3-540-40543-6
Number of pages
433Pages
39-48
Publication identifier
Metadata
Show full item recordAbstract (EN)
Local search has been widely used in combinatorial optimization [3], 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 [13]. We show that it is possible to get in linear time, a \frac3223-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 [12].Subjects / Keywords
Local search; Multicriteria TSP; Approximation algorithmsRelated items
Showing items related by title and author.
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2004) Article accepté pour publication ou publié
-
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 (2014) Chapitre d'ouvrage
-
Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2007) Document de travail / Working paper