Thumbnail

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
2007
Journal name
European Journal of Operational Research
Volume
181
Number
2
Publisher
Elsevier
Pages
620-633
Publication identifier
Metadata
Show full item record
Author(s)
Paschos, Vangelis
Escoffier, Bruno
Abstract (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 satisfiability