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
TypeArticle accepté pour publication ou publié
Journal nameEuropean Journal of Operational Research
MetadataShow full item record
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.
Subjects / KeywordsNP-hard optimization problems; Polynomial approximation; Differential approximation; Satisfiability; Minimum satisfiability
Showing items related by title and author.
Approximation of max independent set, min vertex cover and related problems by moderately exponential algorithms Bourgeois, Nicolas; Escoffier, Bruno; Paschos, Vangelis (2011) Article accepté pour publication ou publié