Show simple item record

dc.contributor.authorAusiello, Giorgio
dc.contributor.authorDemange, Marc
dc.contributor.authorLaura, Luigi
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-11-24T13:27:44Z
dc.date.available2009-11-24T13:27:44Z
dc.date.issued2004
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2525
dc.language.isoenen
dc.subjectOn-line algorithmsen
dc.subjectTraveling Salesman Problemen
dc.subjectQuota TSPen
dc.subject.ddc003en
dc.titleAlgorithms for the on-line quota traveling salesman problemen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherESSEC, Département SID;France
dc.contributor.editoruniversityotherDipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”;Italie
dc.description.abstractenThe Quota Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem. The goal of the traveling salesman is, in this case, to reach a given quota of sales, minimizing the amount of time. In this paper we address the on-line version of the problem, where requests are given over time. We present algorithms for various metric spaces, and analyze their performance in the usual framework of competitive analysis. In particular we present a 2-competitive algorithm that matches the lower bound for general metric spaces. In the case of the halfline metric space, we show that it is helpful not to move at full speed, and this approach is also used to derive the best on-line polynomial time algorithm known so far for the On-Line TSP (in the homing version).en
dc.relation.isversionofjnlnameInformation Processing Letters
dc.relation.isversionofjnlvol92en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2004
dc.relation.isversionofjnlpages89-94en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ipl.2004.06.013en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record