Balanced max 2-sat might not be the hardest
- 11 June 2007
- conference paper
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 189-197
- https://doi.org/10.1145/1250790.1250818
Abstract
No abstract availableKeywords
This publication has 23 references indexed in Scilit:
- Some optimal inapproximability resultsJournal of the ACM, 2001
- On Weighted vs Unweighted Versions of Combinatorial Optimization ProblemsInformation and Computation, 2001
- Zero Knowledge and the Chromatic NumberJournal of Computer and System Sciences, 1998
- A threshold of ln n for approximating set coverJournal of the ACM, 1998
- Proof verification and the hardness of approximation problemsJournal of the ACM, 1998
- Approximate graph coloring by semidefinite programmingJournal of the ACM, 1998
- Probabilistic checking of proofsJournal of the ACM, 1998
- An algorithm for 3-colorable graphsInformation Processing Letters, 1997
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programmingJournal of the ACM, 1995
- Interior Point Methods in Semidefinite Programming with Applications to Combinatorial OptimizationSIAM Journal on Optimization, 1995