Thumbnail - Request a copy

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érence
Date
2003
Conference title
14th International Symposium on Fundamentals of Computation Theory (FCT 2003)
Conference date
2003-08
Conference city
Malmö
Conference country
Suède
Book title
Fundamentals of Computation Theory 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings
Book author
Lingas, Andrzej; Nilsson, Bengt J.
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
2751
Published in
Berlin
ISBN
978-3-540-40543-6
Number of pages
433
Pages
39-48
Publication identifier
Metadata
Show full item record
Author(s)
Angel, Eric
Bampis, Evripidis
Gourvès, Laurent
Abstract (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 algorithms