.879-approximation algorithms for MAX CUT and MAX 2SAT
作者： Michel X. Goemans , David P. Williamson
关键词: Mathematics 、 Maximum cut 、 Approximation algorithm 、 Semidefinite programming 、 Combinatorics 、 Discrete mathematics
摘要:
acm.org
sci-hub.se 参考文章(32)
László Lovász, Alexander Schrijver, Matrix cones, projection representations, and stable set polyhedra Polyhedral Combinatorics. pp. 1- 18 ,(1990)
Uriel Feige, Laszlo Lovasz, Two-prover one-round proof systems: Their power and their problems symposium on the theory of computing. ,(1992)
Bojan Mohar, Svatopluk Poljak, Eigenvalues in Combinatorial Optimization Institute for Mathematics and Its Applications. ,vol. 50, pp. 107- 151 ,(1993) , 10.1007/978-1-4613-8354-3_5
Farid Alizadeh, Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization Siam Journal on Optimization. ,vol. 5, pp. 13- 51 ,(1995) , 10.1137/0805002
M. L. Overton, R. S. Womersley, Optimality Conditions and Duality Theory for Minimizing Sums of the Largest Eigenvalues of Symmetric Matrices ,(2011)
Paul MB Vitányi, None, How well can a graph be n-colored? Discrete Mathematics. ,vol. 34, pp. 69- 80 ,(1981) , 10.1016/0012-365X(81)90023-6
M. Yannakakis, On the approximation of maximum satisfiability symposium on discrete algorithms. ,vol. 17, pp. 1- 9 ,(1992) , 10.1006/JAGM.1994.1045
Michel X. Goemans, David P. Williamson, New ${\bf \frac{3}{4}}$-Approximation Algorithms for the Maximum Satisfiability Problem SIAM Journal on Discrete Mathematics. ,vol. 7, pp. 656- 666 ,(1994) , 10.1137/S0895480192243516
M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization Combinatorica. ,vol. 1, pp. 169- 197 ,(1981) , 10.1007/BF02579273
Charles Delorme, Svatopluk Poljak, Combinatorial properties and complexity of a max-cut approximation The Journal of Combinatorics. ,vol. 14, pp. 313- 333 ,(1993) , 10.1006/EUJC.1993.1035