Show simple item record

dc.contributor.authorAngelelli, Enrico*
dc.contributor.authorBazgan, Cristina*
dc.contributor.authorSperanza, Maria Grazia*
dc.contributor.authorTuza, Zsolt*
dc.date.accessioned2017-01-10T13:04:23Z
dc.date.available2017-01-10T13:04:23Z
dc.date.issued2014
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/16143
dc.language.isoenen
dc.subjectTSPen
dc.subjectRouting problem with profiten
dc.subjectComputational complexityen
dc.subjectApproximation algorithmen
dc.subjectPathen
dc.subjectTreeen
dc.subjectCycleen
dc.subject.ddc003en
dc.subject.classificationjelC.C4.C44en
dc.titleComplexity and approximation for Traveling Salesman Problems with profitsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn TSP with profits we have to find an optimal tour and a set of customers satisfying a specific constraint. In this paper we analyze three different variants of TSP with profits that are NP-hard in general. We study their computational complexity on special structures of the underlying graph, both in the case with and without service times to the customers. We present polynomial algorithms for the polynomially solvable cases and fully polynomial time approximation schemes (FPTAS) for some NP-hard cases.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol531en
dc.relation.isversionofjnldate2014-04
dc.relation.isversionofjnlpages54-65en
dc.relation.isversionofdoi10.1016/j.tcs.2014.02.046en
dc.contributor.countryeditoruniversityotherITALY
dc.contributor.countryeditoruniversityotherHUNGARY
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2017-01-10T12:55:51Z
hal.person.labIds150608*
hal.person.labIds989*
hal.person.labIds150608*
hal.person.labIds246630*
hal.faultCode{"duplicate-entry":{"hal-01430974":{"doi":"1.0"}}}


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