
Differential approximation of MIN SAT, MAX SAT and related problems
Paschos, Vangelis; Escoffier, Bruno (2007), Differential approximation of MIN SAT, MAX SAT and related problems, European Journal of Operational Research, 181, 2, p. 620-633. http://dx.doi.org/10.1016/j.ejor.2005.04.057
View/ Open
Type
Article accepté pour publication ou publiéDate
2007Journal name
European Journal of Operational ResearchVolume
181Number
2Publisher
Elsevier
Pages
620-633
Publication identifier
Metadata
Show full item recordAbstract (EN)
We 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.Subjects / Keywords
NP-hard optimization problems; Polynomial approximation; Differential approximation; Satisfiability; Minimum satisfiabilityRelated items
Showing items related by title and author.
-
Escoffier, Bruno; Paschos, Vangelis (2005) Communication / Conférence
-
Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié
-
Bonnet, Édouard; Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2012) Document de travail / Working paper
-
Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
-
Escoffier, Bruno; Paschos, Vangelis; Tourniaire, Emeric (2014) Article accepté pour publication ou publié