Differential approximation of MIN SAT, MAX SAT and related problems

DOI10.1016/J.EJOR.2005.04.057zbMATH Open1131.90080OpenAlexW1534812271MaRDI QIDQ877035FDOQ877035

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)

Cites Work

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

Cited In (6)

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

   Recommendations

• Differential approximation for optimal satisfiability and related problems 👍 👎
• Approximating MIN 2-SAT and MIN 3-SAT 👍 👎
• Title not available (Why is that?) 👍 👎
• The approximability of constraint satisfaction problems 👍 👎
• Approximating satisfiable satisfiability problems 👍 👎

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)