Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT
Top Cited Papers
- 19 November 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
No abstract availableThis publication has 12 references indexed in Scilit:
- Interactive proofs and approximation: reductions from two provers in one roundPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Approximate graph coloring by semidefinite programmingPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- On the Approximation of Maximum SatisfiabilityJournal of Algorithms, 1994
- On the hardness of approximating minimization problemsPublished by Association for Computing Machinery (ACM) ,1993
- Two-prover one-round proof systemsPublished by Association for Computing Machinery (ACM) ,1992
- Proof verification and hardness of approximation problemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1992
- Optimization, approximation, and complexity classesJournal of Computer and System Sciences, 1991
- On the cut polytopeMathematical Programming, 1986
- The ellipsoid method and its consequences in combinatorial optimizationCombinatorica, 1981
- On the Shannon capacity of a graphIEEE Transactions on Information Theory, 1979