• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Differential approximation of MIN SAT, MAX SAT and related problems

Thumbnail
View/Open
cahier220.pdf (391.5Kb)
Date
2007
Dewey
Recherche opérationnelle
Sujet
NP-hard optimization problems; Polynomial approximation; Differential approximation; Satisfiability; Minimum satisfiability
Journal issue
European Journal of Operational Research
Volume
181
Number
2
Publication date
2007
Article pages
620-633
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/j.ejor.2005.04.057
URI
https://basepub.dauphine.fr/handle/123456789/2097
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Paschos, Vangelis
Escoffier, Bruno
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.