Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
479108 | European Journal of Operational Research | 2007 | 14 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computer Science (General)
Authors
Bruno Escoffier, Vangelis Th. Paschos,