Differential approximation for optimal satisfiability and related problems
From MaRDI portal
Recommendations
- Differential approximation of MIN SAT, MAX SAT and related problems
- On approximation algorithms for the minimum satisfiability problem
- Differential approximation algorithms for some combinatorial optimization problems
- On the differential approximation of MIN SET COVER
- Approximating MIN 2-SAT and MIN 3-SAT
Cites work
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- Computational experience with an interior point algorithm on the satisfiability problem
- scientific article; zbMATH DE number 1303558 (Why is no real title available?)
- scientific article; zbMATH DE number 1330033 (Why is no real title available?)
- scientific article; zbMATH DE number 1114009 (Why is no real title available?)
- On an approximation measure founded on the links between optimization and polynomial approximation theory
- Optimization, approximation, and complexity classes
- Proof verification and the hardness of approximation problems
- Resolution vs. cutting plane solution of inference problems: Some computational experience
- Structure preserving reductions among convex optimization problems
Cited in
(8)- scientific article; zbMATH DE number 1114011 (Why is no real title available?)
- Differential approximation of NP-hard problems with equal size feasible solutions
- A survey on the structure of approximation classes
- COMPLETENESS IN DIFFERENTIAL APPROXIMATION CLASSES
- On the complexity of winner determination and strategic control in conditional approval voting
- Differential approximation of MIN SAT, MAX SAT and related problems
- A better differential approximation ratio for symmetric TSP
- New differential approximation algorithm for \(k\)-customer vehicle routing problem
This page was built for publication: Differential approximation for optimal satisfiability and related problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1869721)
