Differential approximation of MIN SAT, MAX SAT and related problems

DOI10.1016/j.ejor.2005.04.057zbMath1131.90080OpenAlexW1534812271MaRDI QIDQ877035

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

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

Related Items (5)

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

Cites Work

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

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