• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
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
http://dx.doi.org/10.1007/978-3-540-45077-1_5
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

Related items

Showing items related by title and author.

  • Thumbnail
    Approximating the Pareto curve with local search for the bicriteria TSP(1,2) problem 
    Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2004) Article accepté pour publication ou publié
  • Thumbnail
    En approchant la courbe de Pareto à l'aide de la recherche locale pour le problème du voyageur de commerce bicritère avec des distances 1 et 2 
    Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2003) Communication / Conférence
  • Thumbnail
    (Non)-Approximability for the multi-criteria TSP(1,2) 
    Monnot, Jérôme; Gourvès, Laurent; Bampis, Evripidis; Angel, Eric (2005) Communication / Conférence
  • Thumbnail
    Polynomial Approximation for Multicriteria Combinatorial Optimization Problems 
    Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2014) Chapitre d'ouvrage
  • Thumbnail
    On the hitting set of bundles problem 
    Angel, Eric; Bampis, Evripidis; Gourvès, Laurent (2007) Document de travail / Working paper
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo