Afficher la notice abrégée

dc.contributor.authorMonnot, Jérôme
dc.contributor.authorGourvès, Laurent
dc.contributor.authorBampis, Evripidis
dc.contributor.authorAngel, Eric
dc.date.accessioned2010-12-15T15:42:43Z
dc.date.available2010-12-15T15:42:43Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5310
dc.language.isoenen
dc.subjectoptimization problemsen
dc.subjectmulti-criteriaen
dc.subjectapproximability of multi-criteriaen
dc.subjectapproximation algorithmen
dc.subjectNP-completeen
dc.subjecttraveling salesman problemen
dc.subject.ddc003en
dc.title(Non)-Approximability for the multi-criteria TSP(1,2)en
dc.typeCommunication / Conférence
dc.contributor.editoruniversityotherLAMI UMR 8042, Université d'Evry;France
dc.description.abstractenMany papers deal with the approximability of multi-criteria optimization problems but only a small number of non-approximability results, which rely on NP-hardness, exist in the literature. In this paper, we provide a new way of proving non-approximability results which relies on the existence of a small size good approximating set (i.e. it holds even in the unlikely event of P = NP ). This method may be used foseveral problems but here we illustrate it for a multi-criteria version of the traveling salesman problem with distances one and two (T SP (1, 2)). Following the article of Angel et al. (FCT 2003) who presented an approximation algorithm for the bi-criteria T SP (1, 2), we extend and improve the result to any number k of criteria.en
dc.identifier.citationpages329-340
dc.relation.ispartofseriestitleLecture Notes in Computer Science
dc.relation.ispartofseriesnumber3623
dc.relation.ispartoftitleFundamentals of Computation Theory 15th International Symposium, FCT 2005, Lübeck, Gemany, August 17-20, 2005, Proceedings
dc.relation.ispartofeditorReischuk, Rüdiger
dc.relation.ispartofeditorLiskiewicz, Maciejen_US
dc.relation.ispartofpublnameSpringeren_US
dc.relation.ispartofpublcityBerlin
dc.relation.ispartofdate2005
dc.relation.ispartofpages576
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/11537311
dc.identifier.urlsitehttp://hal.archives-ouvertes.fr/hal-00115511/en/
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-28193-1
dc.relation.conftitleFundamentals of Computation Theory (FCT 2005)en
dc.relation.confdate2005-08
dc.relation.confcityLübecken
dc.relation.confcountryAllemagneen
dc.identifier.doihttp://dx.doi.org/10.1007/11537311_29


Fichiers attachés à cette notice

FichiersTailleFormatConsulter

Il n'y a pas de fichiers associés à cette notice.

Ce document fait partie de la (des) collection(s) suivante(s)

Afficher la notice abrégée