
Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014), Approximating MAX SAT by Moderately Exponential and Parameterized Algorithms, Theoretical Computer Science, 560, 2, p. 147-157. 10.1016/j.tcs.2014.10.039
Voir/Ouvrir
Type
Article accepté pour publication ou publiéDate
2014Nom de la revue
Theoretical Computer ScienceVolume
560Numéro
2Éditeur
Elsevier
Pages
147-157
Identifiant publication
Métadonnées
Afficher la notice complèteAuteur(s)
Escoffier, BrunoLaboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Paschos, Vangelis
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Tourniaire, Emeric
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Résumé (EN)
We 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.Mots-clés
Exponential time algorithms; Approximation algorithms; Max SATPublications associées
Affichage des éléments liés par titre et auteur.
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Communication / Conférence
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper
-
Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper
-
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié