Show simple item record

dc.contributor.authorAngel, Eric
dc.contributor.authorBampis, Evripidis
dc.contributor.authorGourvès, Laurent
dc.date.accessioned2011-04-05T13:51:25Z
dc.date.available2011-04-05T13:51:25Z
dc.date.issued2004
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5915
dc.language.isoenen
dc.subjectLocal searchen
dc.subjectMulticriteria TSPen
dc.subjectApproximation algorithmsen
dc.subject.ddc003en
dc.titleApproximating the Pareto curve with local search for the bicriteria TSP(1,2) problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenLocal 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).en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol310en
dc.relation.isversionofjnlissue1-3en
dc.relation.isversionofjnldate2004
dc.relation.isversionofjnlpages135-146en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0304-3975(03)00376-1en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record