Show simple item record

dc.contributor.authorEscoffier, Bruno*
dc.contributor.authorPaschos, Vangelis*
dc.contributor.authorTourniaire, Emeric*
dc.date.accessioned2011-05-19T13:05:20Z
dc.date.available2011-05-19T13:05:20Z
dc.date.issued2012
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/6304
dc.language.isoenen
dc.subjectmax sat problem
dc.subjectmoderately exponential algorithms
dc.subjectmoderately exponential approximation
dc.subject.ddc003en
dc.titleApproximating MAX SAT by moderately exponential algorithms
dc.typeCommunication / Conférence
dc.description.abstractenWe study approximation of the max sat problem by moderately exponential algorithms.The general goal of the issue of moderately exponential approximation is to catch-up onpolynomial inapproximability, by providing algorithms achieving, with worst-case runningtimes importantly smaller than those needed for exact computation, approximation ratiosunachievable in polynomial time. We develop several approximation techniques that can beapplied to max sat in order to get approximation ratios arbitrarily close to 1.
dc.identifier.citationpages622
dc.relation.ispartoftitleTheory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings
dc.relation.ispartofeditorLi, Angsheng
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2012
dc.relation.ispartofurlhttp://dx.doi.org/10.1007/978-3-642-29952-0
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-642-29951-3
dc.relation.conftitle9th Annual Conference on Theory and Applications of Models of Computation , TAMC 2012
dc.relation.confdate2012-05
dc.relation.confcityBeijing
dc.relation.confcountryChina
dc.identifier.doi10.1007/978-3-642-29952-0_23
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2017-02-09T16:18:21Z
hal.person.labIds989*
hal.person.labIds989*
hal.person.labIds989*
hal.identifierhal-01509537*


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record