Show simple item record

Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms

hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorEscoffier, Bruno
HAL ID: 5124
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorPaschos, Vangelis
hal.structure.identifierLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
dc.contributor.authorTourniaire, Emeric
dc.date.accessioned2020-07-22T10:44:37Z
dc.date.available2020-07-22T10:44:37Z
dc.date.issued2014
dc.identifier.issn0304-3975
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/20957
dc.language.isoenen
dc.subjectExponential time algorithmsen
dc.subjectApproximation algorithmsen
dc.subjectMax SATen
dc.subject.ddc005en
dc.titleApproximating MAX SAT by Moderately Exponential and Parameterized Algorithmsen
dc.typeArticle accepté pour publication ou publié
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 on polynomial inapproximability, by providing algorithms achieving, with worst-case running times importantly smaller than those needed for exact computation, approximation ratios unachievable in polynomial time. We develop several approximation techniques that can be applied to max sat in order to get approximation ratios arbitrarily close to 1.en
dc.relation.isversionofjnlnameTheoretical Computer Science
dc.relation.isversionofjnlvol560en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2014-12
dc.relation.isversionofjnlpages147-157en
dc.relation.isversionofdoi10.1016/j.tcs.2014.10.039en
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidatenonen
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewedouien
dc.relation.Isversionofjnlpeerreviewedouien
dc.date.updated2020-07-22T10:41:51Z
hal.author.functionaut
hal.author.functionaut
hal.author.functionaut


Files in this item

Thumbnail
Name:
Approximating_MAX.pdf
Size:
498.0Kb
Format:
PDF
View/Open

This item appears in the following Collection(s)

Show simple item record