Show simple item record

dc.contributor.authorAusiello, Giorgio
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2009-10-12T13:39:31Z
dc.date.available2009-10-12T13:39:31Z
dc.date.issued2006
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2209
dc.language.isoenen
dc.subjectCompleteness in approximation classesen
dc.subjectApproximation preserving reductionen
dc.subjectPolynomial approximationen
dc.subjectNP-hard optimization problemsen
dc.subjectComputing scienceen
dc.subjectComplexity theoryen
dc.subjectCombinatorial optimizationen
dc.subject.ddc003en
dc.titleReductions, completeness and the hardness of approximabilityen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherDipartimento di Informatica e Sistemistica, Università di Roma “La Sapienza”;Italie
dc.description.abstractenIn computability and in complexity theory reductions are widely used for mapping sets into sets in order to prove undecidability or hardness results. In the study of the approximate solvability of hard discrete optimization problems, suitable kinds of reductions, called approximation preserving reductions, can also be used to transfer from one problem to another either positive results (solution techniques) or negative results (non-approximability results). In this paper various kinds of approximation preserving reductions are surveyed and their properties discussed. The role of completeness under approximation preserving reductions is also analyzed and its relationship with hardness of approximability is explained.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol172en
dc.relation.isversionofjnlissue3en
dc.relation.isversionofjnldate2006
dc.relation.isversionofjnlpages719-739en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2005.06.006en
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