Approximating the value of two power proof systems, with applications to MAX 2SAT and MAX DICUT
Authors:
- U. FeigeUFU. Feige
- M. GoemansMGM. Goemans
- 19 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 182-189
Abstract
No abstract availableThis publication has 12 references indexed in Scilit:
- Interactive proofs and approximation: reductions from two provers in one round2002
- Approximate graph coloring by semidefinite programming2002
- On the Approximation of Maximum SatisfiabilityJournal of Algorithms, 1994
- On the hardness of approximating minimization problems1993
- Two-prover one-round proof systems1992
- Proof verification and hardness of approximation problems1992
- 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