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

Voir/Ouvrir
Type
Article accepté pour publication ou publié
Date
2007
Nom de la revue
European Journal of Operational Research
Volume
181
Numéro
2
Éditeur
Elsevier
Pages
620-633
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Paschos, Vangelis
Escoffier, Bruno
Résumé (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.
Mots-clés
NP-hard optimization problems; Polynomial approximation; Differential approximation; Satisfiability; Minimum satisfiability