Show simple item record

dc.contributor.authorPaschos, Vangelis
dc.contributor.authorEscoffier, Bruno
dc.date.accessioned2009-10-03T07:22:01Z
dc.date.available2009-10-03T07:22:01Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2097
dc.language.isoenen
dc.subjectNP-hard optimization problemsen
dc.subjectPolynomial approximationen
dc.subjectDifferential approximationen
dc.subjectSatisfiabilityen
dc.subjectMinimum satisfiabilityen
dc.subject.ddc003en
dc.titleDifferential approximation of MIN SAT, MAX SAT and related problemsen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe present differential approximation results (both positive and negative) for optimal satisfiability, optimal constraint satisfaction, and some of the most popular restrictive versions of them. As an important corollary, we exhibit an interesting structural difference between the landscapes of approximability classes in standard and differential paradigms.en
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol181en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2007
dc.relation.isversionofjnlpages620-633en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2005.04.057en
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