
Approximating MAX SAT by moderately exponential algorithms
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012), Approximating MAX SAT by moderately exponential algorithms, in Li, Angsheng, Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. Proceedings, Springer : Berlin Heidelberg, p. 622. 10.1007/978-3-642-29952-0_23
View/ Open
Type
Communication / ConférenceDate
2012Conference title
9th Annual Conference on Theory and Applications of Models of Computation , TAMC 2012Conference date
2012-05Conference city
BeijingConference country
ChinaBook title
Theory and Applications of Models of Computation - 9th Annual Conference, TAMC 2012, Beijing, China, May 16-21, 2012. ProceedingsBook author
Li, AngshengPublisher
Springer
Published in
Berlin Heidelberg
ISBN
978-3-642-29951-3
Pages
622
Publication identifier
Metadata
Show full item recordAuthor(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]
Abstract (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 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.Subjects / Keywords
max sat problem; moderately exponential algorithms; moderately exponential approximationRelated items
Showing items related by title and author.
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014) Article accepté pour publication ou publié
-
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
-
Paschos, Vangelis; Escoffier, Bruno; Bourgeois, Nicolas (2009) Article accepté pour publication ou publié
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2009) Communication / Conférence