Differential approximation of MIN SAT, MAX SAT and related problems

We present differential approximation results (both positive and negative) for optimal satis ability, 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.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00958506
Author Escoffier, Bruno, Paschos, Vangelis
Maintainer CCSD
Last Updated May 6, 2026, 01:42 (UTC)
Created May 6, 2026, 01:42 (UTC)
Identifier hal-00958506
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision (LAMSADE) ; Université Paris Dauphine-PSL ; Université Paris Sciences et Lettres (PSL)-Université Paris Sciences et Lettres (PSL)-Centre National de la Recherche Scientifique (CNRS)
creator Escoffier, Bruno
date 2004-06-22T00:00:00
harvest_object_id 68003ed2-87e2-45f4-b6f0-66772eaca01b
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-06-13T00:00:00
set_spec type:UNDEFINED