Show simple item record

dc.contributor.authorAusiello, Giorgio
dc.contributor.authorEscoffier, Bruno
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2011-04-04T12:17:51Z
dc.date.available2011-04-04T12:17:51Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5878
dc.language.isoenen
dc.subjectReoptimizationen
dc.subjectTraveling Salesmanen
dc.subject.ddc003en
dc.titleReoptimization of minimum and maximum traveling salesman's toursen
dc.typeCommunication / Conférence
dc.description.abstractenIn this paper, reoptimization versions of the traveling salesman problem (TSP) are addressed. Assume that an optimum solution of an instance is given and the goal is to determine if one can maintain a good solution when the instance is subject to minor modifications. We study the case where nodes are inserted in, or deleted from, the graph. When inserting a node, we show that the reoptimization problem for MinTSP is approximable within ratio 4/3 if the distance matrix is metric. We show that, dealing with metric MaxTSP, a simple heuristic is asymptotically optimum when a constant number of nodes are inserted. In the general case, we propose a 4/5-approximation algorithm for the reoptimization version of MaxTSP.en
dc.identifier.citationpages196-207en
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber4059
dc.relation.ispartoftitleAlgorithm Theory - SWAT 2006 10th Scandinavian Workshop on Algorithm Theory, Riga, Latvia, July 6-8, 2006, Proceedingsen
dc.relation.ispartofeditorArge, Lars
dc.relation.ispartofeditorFreivalds, Rusins
dc.relation.ispartofpublnameSpringeren
dc.relation.ispartofpublcityBerlinen
dc.relation.ispartofdate2006
dc.relation.ispartofpages436en
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/11785293en
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-35753-7en
dc.relation.conftitle10th Scandinavian Workshop on Algorithm Theory (SWAT 2006)en
dc.relation.confdate2006-07
dc.relation.confcityRigaen
dc.relation.confcountryLettonieen
dc.identifier.doihttp://dx.doi.org/10.1007/11785293_20


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record