Differential approximation of MIN SAT, MAX SAT and related problems
Bruno Escoffier, Vangelis Th. Paschos · 2004
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 impor-tant corollary, we exhibit an interesting structural difference between the landscapes of approximability classes in standard and differential paradigms. 1 Introduction and