Differential approximation of MIN SAT, MAX SAT and related problems

DOI10.1016/J.EJOR.2005.04.057MaRDI QIDQ877035zbMATH OpenOpenAlexFDO

Authors Bruno Escoffier, Vangelis Th. Paschos

Publication date 19 April 2007

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2005.04.057

zbMATH Keywords

polynomial approximationsatisfiabilitymaximum satisfiabilitydifferential approximationminimum satisfiabilityNP-hard optimization problems

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• Differential approximation for optimal satisfiability and related problems
• Approximating MIN 2-SAT and MIN 3-SAT
• scientific article; zbMATH DE number 1979522
• The approximability of constraint satisfaction problems
• Approximating satisfiable satisfiability problems

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1302170 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1865680 (Why is no real title available?)
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Computational experience with an interior point algorithm on the satisfiability problem
• Derandomized graph products
• Differential approximation for optimal satisfiability and related problems
• Gadgets, Approximation, and Linear Programming
• On dependent randomized rounding algorithms
• Optimization, approximation, and complexity classes
• Resolution vs. cutting plane solution of inference problems: Some computational experience
• Some optimal inapproximability results
• Structure in Approximation Classes

Cited in

(6)

• Differential approximation algorithm of FSMVRP
• Differential approximation for optimal satisfiability and related problems
• New differential approximation algorithm for \(k\)-customer vehicle routing problem
• Polynomial approximation: a structural and operational study. (Abstract of thesis)
• A better differential approximation ratio for symmetric TSP
• A survey on the structure of approximation classes

This page was built for publication: Differential approximation of MIN SAT, MAX SAT and related problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q877035)