Show simple item record

Polynomial approximation algorithms with performance guarantees: an introduction-by-example

dc.contributor.authorDemange, Marc
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-10-12T13:06:37Z
dc.date.available2009-10-12T13:06:37Z
dc.date.issued2005
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2204
dc.language.isoenen
dc.subjectTraveling salesmanen
dc.subjectComplexity theoryen
dc.subjectComputing scienceen
dc.subjectCombinatorial optimizationen
dc.subject.ddc003en
dc.titlePolynomial approximation algorithms with performance guarantees: an introduction-by-exampleen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherESSEC;France
dc.description.abstractenWe present a short overview on polynomial approximation of NP-hard problems. We present the main approximability classes together with examples of problems belonging to them. We also describe the general concept of approximability preserving reductions together with a discussion about their capacities and their limits. Finally, we present a quick description of what it is commonly called inapproximability results. Such results provide limits on the approximability of the problems tackled.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol165en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2005
dc.relation.isversionofjnlpages555-568en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2004.03.021en
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