{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2020,3,1]],"date-time":"2020-03-01T22:03:30Z","timestamp":1583100210640},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[1995,11]]},"DOI":"10.1145\/227683.227684","type":"journal-article","created":{"date-parts":[[2002,7,27]],"date-time":"2002-07-27T11:25:57Z","timestamp":1027769157000},"page":"1115-1145","source":"Crossref","is-referenced-by-count":1471,"title":["Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming"],"prefix":"10.1145","volume":"42","author":[{"given":"Michel X.","family":"Goemans","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, Cambridge"}]},{"given":"David P.","family":"Williamson","sequence":"additional","affiliation":[{"name":"IBM T. J. Watson Research Center, Yorktown Heights, NY"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","article-title":"Interior point methods in semidefinite programming with applications to ~combinatorial optimization","volume":"5","author":"~ALIZADEH F.","year":"1995","journal-title":"SIAM J. Optimiz."},{"key":"e_1_2_1_2_1","unstructured":"Proceedings of the 33rd Annual Symposium on Founda- ~tions of Computer Science. IEEE New York Proceedings of the 33rd Annual Symposium on Founda- ~tions of Computer Science. IEEE S. ~ARORA C. LUND R. MOTWANI M. SUDAN M. SZEGEDY Proof verification and ~hardness of approximation problems 1992 14 23"},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1016\/0196-6774(81)90020-1","article-title":"A linear time approximation algorithm for the weighted ~verllex cover problem","volume":"2","author":"~BAR-YEHUDA R.","year":"1981","journal-title":"J. Algorithms"},{"key":"e_1_2_1_4_1","DOI":"10.1287\/opre.36.3.493","doi-asserted-by":"publisher"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/BF02574037","article-title":"Problems of distance geometry and convex properties of quadratic ~maps","volume":"13","author":"~BARV NOK","year":"1995","journal-title":"Disc. Computat. Geom."},{"key":"e_1_2_1_6_1","unstructured":"Proceedings of the 36th Annual Symposium on Foundations of Computer ~Science. IEEE Los Alamitos Calif. Proceedings of the 36th Annual Symposium on Foundations of Computer ~Science. IEEE Los Alamitos Calif. M. ~BELLARE O. GOLDREICH M. SUDAN Free bits PCP and non-approximability-- ~Towards tight results 1995 422 431 10.5555\/795662.796263"},{"key":"e_1_2_1_7_1","unstructured":"~BERGER M. 1987. Geometry II. Springer-Verlag Berlin. ~BERGER M. 1987. Geometry II. Springer-Verlag Berlin."},{"key":"e_1_2_1_8_1","unstructured":"~BONDY J. A. AND MURTY U. S.R. 1976. Graph Theory with Applications. American Elsevier ~Publishing New York N.Y. ~BONDY J. A. AND MURTY U. S.R. 1976. Graph Theory with Applications. American Elsevier ~Publishing New York N.Y."},{"key":"e_1_2_1_9_1","unstructured":"~BOYD S. EL GHAOUI L. FERON E. AND BALAKRISHNAN V. 1994. Linear Matrix Inequalities in ~System and Control Theory. SIAM Philadelphia Pa. ~BOYD S. EL GHAOUI L. FERON E. AND BALAKRISHNAN V. 1994. Linear Matrix Inequalities in ~System and Control Theory. SIAM Philadelphia Pa."},{"key":"e_1_2_1_10_1","unstructured":"Algorithms-ESA '95 Spirakis ed. Lecture Notes in Computer Science Algorithms-ESA '95 979 B. ~CHOR SUDAN A geometric approach to betweenness 1995 10.5555\/647905.739628"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1007\/BF01420337","article-title":"A note on extreme positive definite matrices. ~Math","volume":"244","author":"~CHRISTENSEN J.","year":"1979","journal-title":"Annalen"},{"key":"e_1_2_1_12_1","DOI":"10.1006\/eujc.1993.1035","doi-asserted-by":"publisher"},{"key":"e_1_2_1_13_1","DOI":"10.1007\/BF01585184","doi-asserted-by":"publisher"},{"key":"e_1_2_1_14_1","DOI":"10.1016\/0012-365X(93)90151-I","doi-asserted-by":"publisher"},{"key":"e_1_2_1_15_1","unstructured":"~EULER L. 1781. De mensura angulorum solidorum. Petersburg. ~EULER L. 1781. De mensura angulorum solidorum. Petersburg."},{"key":"e_1_2_1_16_1","unstructured":"Proceedings of the 3rd Israel Symposium ~on Theory of Computing and Systems. IEEE Computer Society Press Los Alamitos Calif. ~pp. 182-189 Proceedings of the 3rd Israel Symposium ~on Theory of Computing and Systems. IEEE Computer Society Press Los Alamitos Calif. ~pp. 182-189 U. ~FEIGE M.X. GOEMANS Approximating the value of two prover proof systems ~with applications to MAX 2SAT and MAX DICUT 1995 10.5555\/527073.881418"},{"key":"e_1_2_1_17_1","unstructured":"Proceedings of the 24th Annual ACM Symposium on the Theory of Computing ~(Victoria S.C. Canada May 4-6). ACM New York Proceedings of the 24th Annual ACM Symposium on the Theory of Computing ~(Victoria S.C. Canada May 4-6). ACM E U ~FE SZ L LOVJ Two-prover one-round proof systems: Their power and their ~problems 1992 733 744 10.1145\/129712.129783 10.1145\/129712.129783 10.1145\/129712.129783"},{"key":"e_1_2_1_18_1","unstructured":"~FRIEZE A. AND JERRUM M. 1996. Improved approximation algorithms for MAX k-CUT and ~MAX BISECTION. Algorithmica to appear. ~FRIEZE A. AND JERRUM M. 1996. Improved approximation algorithms for MAX k-CUT and ~MAX BISECTION. Algorithmica to appear."},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","first-page":"237","DOI":"10.1016\/0304-3975(76)90059-1","article-title":"Some simplified NP-complete graph ~problems","volume":"1","author":"~GAREY M.","year":"1976","journal-title":"Theoret. Comput. Sci."},{"key":"e_1_2_1_20_1","unstructured":"~GIRARD A. 1629. De la mesure de la superficie des triangles et polygones sph6riques. Appendix ~to \"Invention nouvelle en l'alg~bre\". Amsterdam. ~GIRARD A. 1629. De la mesure de la superficie des triangles et polygones sph6riques. Appendix ~to \"Invention nouvelle en l'alg~bre\". Amsterdam."},{"key":"e_1_2_1_21_1","unstructured":"Proceedings of the 26th Annual ACM Symposium on the Theory of ~Computing (Montreal Que. Canada May 23-25) New York Proceedings of the 26th Annual ACM Symposium on the Theory of ~Computing (Montreal Que. Canada May 23-25) M. X. ~GOEMANS D. P. WILLIAMSON 878-approximation algorithms for MAX ~CUT and MAX 2SAT 1994 422 431 10.1145\/195058.195216 10.1145\/195058.195216 10.1145\/195058.195216"},{"key":"e_1_2_1_22_1","DOI":"10.1137\/S0895480192243516","doi-asserted-by":"publisher"},{"key":"e_1_2_1_23_1","unstructured":"~GOLUB G. H. AND VAN LOAN C.F. 1983. Matrix Computations. The Johns Hopkins Uniw:r- ~sity Press Baltimore Md. ~GOLUB G. H. AND VAN LOAN C.F. 1983. Matrix Computations. The Johns Hopkins Uniw:r- ~sity Press Baltimore Md."},{"key":"e_1_2_1_24_1","unstructured":"~GRONE R. PIERCE S. AND WATKINS W. 1990. Extremal correlation matrices. Lin. Algebra ~Appl. 134 63-70. ~GRONE R. PIERCE S. AND WATKINS W. 1990. Extremal correlation matrices. Lin. Algebra ~Appl. 134 63-70."},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","article-title":"The ellipsoid method and its conse- ~quenLces in combinatorial optimization","volume":"1","author":"~GR CHEL","year":"1981","journal-title":"Combinatorica"},{"key":"e_1_2_1_26_1","unstructured":"~GR~STSCHEL M. LOVXSZ L. AND SCHRIJVER A. 1988. Geometric Algorithms and Combinatorial ~Optimization. Springer-Verlag Berlin. ~GR~STSCHEL M. LOVXSZ L. AND SCHRIJVER A. 1988. Geometric Algorithms and Combinatorial ~Optimization. Springer-Verlag Berlin."},{"key":"e_1_2_1_27_1","unstructured":"~HADLOCK F. 1975. Finding a maximum cut of a planar graph in polynomial time. SIAM J. ~Comput. 4 221-225. ~HADLOCK F. 1975. Finding a maximum cut of a planar graph in polynomial time. SIAM J. ~Comput. 4 221-225."},{"key":"e_1_2_1_28_1","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1142\/S0129626492000301","article-title":"Approximating maximum 2-CNF satisfiability","volume":"2","author":"~HAGLIN D.J.","year":"1992","journal-title":"Paral. Proc. Lett."},{"key":"e_1_2_1_29_1","DOI":"10.1109\/12.67327","doi-asserted-by":"publisher"},{"key":"e_1_2_1_30_1","doi-asserted-by":"crossref","first-page":"555","DOI":"10.1137\/0211045","article-title":"Approximation algorithms for the set covering and vertex cover ~problems","volume":"11","author":"~HOCHBAUM D. S.","year":"1982","journal-title":"SIAM J. Comput."},{"key":"e_1_2_1_31_1","unstructured":"~HOFMEISTER T. AND LEFMANN H. 1995. A combinatorial design approach to MAXCUT. In ~Proceedings of the 13th Symposium on Theoretical Aspects of Computer Science. To appear. ~HOFMEISTER T. AND LEFMANN H. 1995. A combinatorial design approach to MAXCUT. In ~Proceedings of the 13th Symposium on Theoretical Aspects of Computer Science. To appear."},{"key":"e_1_2_1_32_1","unstructured":"~HOMER S. AND PEINAr)O M. A highly parallel implementation of the Goemans\/Williamson ~algorithm to approximate MaxCut. Manuscript. ~HOMER S. AND PEINAr)O M. A highly parallel implementation of the Goemans\/Williamson ~algorithm to approximate MaxCut. Manuscript."},{"key":"e_1_2_1_33_1","unstructured":"Proceedings of the 35th Annual Symposium on Foundations of Computer ~Science. IEEE New York Proceedings of the 35th Annual Symposium on Foundations of Computer ~Science. IEEE D. ~KARGER R. MOTWANI M. SUDAN Approximate graph coloring by semidefinite ~programming 1994 2 13"},{"key":"e_1_2_1_34_1","author":"~K XRP","first-page":"85","volume-title":"Complexity of Computer ~Computations"},{"key":"e_1_2_1_35_1","unstructured":"~KNUTH D.E.\n 1981.\n \n \n \n Seminumerical Algorithms\n . Vol. \n 2\n of \n The Art of Computer Programming\n . ~Addison-Wesley Reading Mass\n . ~KNUTH D.E. 1981. Seminumerical Algorithms. Vol. 2 of The Art of Computer Programming. ~Addison-Wesley Reading Mass."},{"key":"e_1_2_1_36_1","unstructured":"~LANCASTER P. AND TISMENETSKY M. 1985. The Theory of Matrices. Academic Press Orlando ~Fla. ~LANCASTER P. AND TISMENETSKY M. 1985. The Theory of Matrices. Academic Press Orlando ~Fla."},{"key":"e_1_2_1_37_1","unstructured":"~LAURENT M. AND POLJAK S. 1996. On the facial structure of the set of correlation matrices. ~SIAM J. Matrix Anal. and Appl. to appear. 10.1137\/0617031 ~LAURENT M. AND POLJAK S. 1996. On the facial structure of the set of correlation matrices. ~SIAM J. Matrix Anal. and Appl. to appear. 10.1137\/0617031"},{"key":"e_1_2_1_38_1","unstructured":"~LI C.-K. AND TAM B.-S. 1994. A note on extreme correlation matrices. SIAM J. Matrix Anal. ~and Appl. J5 903-908. 10.1137\/S0895479892240683 ~LI C.-K. AND TAM B.-S. 1994. A note on extreme correlation matrices. SIAM J. Matrix Anal. ~and Appl. J5 903-908. 10.1137\/S0895479892240683"},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/BF03220000","article-title":"Extreme points of a convex subset of the cone of positive definite matrices. ~Math","volume":"253","author":"~LOEWY R.","year":"1980","journal-title":"Annalen."},{"key":"e_1_2_1_40_1","author":"~L","first-page":"1","year":"1979","article-title":"On the Shannon capacity of a graph","journal-title":"IEEE Trans. Inf. Theory IT-25"},{"key":"e_1_2_1_41_1","first-page":"317","article-title":"Self-dual polytopes and the chromatic number of distance graphs on the ~sphere. Acta Sci","volume":"45","author":"~L","year":"1983","journal-title":"Math."},{"key":"e_1_2_1_42_1","unstructured":"~LovAsz L. 1992. Combinatorial optimization: Some problems and trends. DIMACS Technical ~Report 92-53. ~LovAsz L. 1992. Combinatorial optimization: Some problems and trends. DIMACS Technical ~Report 92-53."},{"key":"e_1_2_1_43_1","unstructured":"~L\n ov\n J.\n \n \n \n sz L. AND SCHRIJVER A\n . \n 1989\n . Matrix cones projection representations and stable set ~polyhedra. In Polyhedral Combinatorics vol. \n 1\n of \n DIMACS Series in Discrete Mathematics and ~Theoretical Computer Science\n . \n American Mathematical Society Providence R.I. ~LovJ. sz L. AND SCHRIJVER A. 1989. Matrix cones projection representations and stable set ~polyhedra. In Polyhedral Combinatorics vol. 1 of DIMACS Series in Discrete Mathematics and ~Theoretical Computer Science. American Mathematical Society Providence R.I."},{"key":"e_1_2_1_44_1","author":"~L","first-page":"166","year":"1990","article-title":"Cones of matrices and setfunctions, and 0-1 optimiza- ~tion","journal-title":"SIAM J. Optimiz."},{"key":"e_1_2_1_45_1","unstructured":"Proceedings of the 36th Annual Symposium on Foundations of Computer ~Science. IEEE Los Alamitos Calif. Proceedings of the 36th Annual Symposium on Foundations of Computer ~Science. IEEE Los Alamitos Calif. S. ~MAHAJAN H. RAMESH Derandomizing semidefinite programming based approxi- ~mation algorithms 1995 162 163 10.5555\/795662.796317"},{"key":"e_1_2_1_46_1","unstructured":"~MOHAR B. AND \n POLJAK S.\n 1993.\n \n \n \n Eigenvalue methods in combinatorial optimization. In ~Combinatorial and Graph-Theoretic Problems in Linear Algebra vol. \n 50\n of \n The IMA Volumes in ~Mathematics and Its Applications\n . R. Brualdi S.\n Friedland and V. Klee eds. \n Springer-Verlag ~New York. ~MOHAR B. AND POLJAK S. 1993. Eigenvalue methods in combinatorial optimization. In ~Combinatorial and Graph-Theoretic Problems in Linear Algebra vol. 50 of The IMA Volumes in ~Mathematics and Its Applications. R. Brualdi S. Friedland and V. Klee eds. Springer-Verlag ~New York."},{"key":"e_1_2_1_47_1","unstructured":"~NESTEROV Y. AND NEMIROVSKII A. 1989. Self-Concordant Functions and Polynomial Time ~Methods in Convex Programming. Central Economic and Mathematical Institute Academy of ~Science Moscow CIS. ~NESTEROV Y. AND NEMIROVSKII A. 1989. Self-Concordant Functions and Polynomial Time ~Methods in Convex Programming. Central Economic and Mathematical Institute Academy of ~Science Moscow CIS."},{"key":"e_1_2_1_48_1","unstructured":"~NESTEROV ~. AND NEMIROVSKII A. 1994. Interior Point Polynomial Methods in Convex ?ro- ~gramming. Society for Industrial and Applied Mathematics Philadelphia Pa. ~NESTEROV ~. AND NEMIROVSKII A. 1994. Interior Point Polynomial Methods in Convex ?ro- ~gramming. Society for Industrial and Applied Mathematics Philadelphia Pa."},{"key":"e_1_2_1_49_1","unstructured":"~ORLOVA G. I. AND DORFMAN Y.G. 1972. Finding the maximal cut in a graph. Eng. Cyber. 10 ~502-506. ~ORLOVA G. I. AND DORFMAN Y.G. 1972. Finding the maximal cut in a graph. Eng. Cyber. 10 ~502-506."},{"key":"e_1_2_1_50_1","DOI":"10.1137\/0613006","doi-asserted-by":"publisher"},{"key":"e_1_2_1_51_1","DOI":"10.1007\/BF01585173","doi-asserted-by":"publisher"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","article-title":"Optimization, approximation, and complex- ~ity classes","volume":"43","author":"~PAPADIM RIOU","year":"1991","journal-title":"J. Comput. Syst. Sci."},{"key":"e_1_2_1_53_1","author":"~PATAKI G.","volume-title":"eport MSRR-604, GSIA. Carnegie-Mellon Univ."},{"key":"e_1_2_1_54_1","unstructured":"~PATAKI G. 1995. On cone-LP's and semi-definite programs: Facial structure basic solutions ~and the simplex method. GSIA Working paper WP 1995-03 Carnegie-Mellon Univ. Pittsburgh ~Pa. ~PATAKI G. 1995. On cone-LP's and semi-definite programs: Facial structure basic solutions ~and the simplex method. GSIA Working paper WP 1995-03 Carnegie-Mellon Univ. Pittsburgh ~Pa."},{"key":"e_1_2_1_55_1","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF02238072","article-title":"Node and edge relaxations of the max-cut problem","volume":"2","author":"~POLJAK S.","year":"1994","journal-title":"Comput- ~ing"},{"key":"e_1_2_1_56_1","unstructured":"~POLJAK S. AND RENDL F. 1995a. Nonpolyhedral relaxations of graph-bisection problems. ~SIAM J. Optim. to appear. ~POLJAK S. AND RENDL F. 1995a. Nonpolyhedral relaxations of graph-bisection problems. ~SIAM J. Optim. to appear."},{"key":"e_1_2_1_57_1","DOI":"10.1016\/0166-218X(94)00155-7","doi-asserted-by":"publisher"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","first-page":"519","DOI":"10.4153\/CJM-1982-036-8","article-title":"A polynomial algorithm for constructing a large bipartite ~subgraph, with an application to a satisfiability problem","volume":"34","author":"~POLJAK S.","year":"1982","journal-title":"Can. J. Math."},{"key":"e_1_2_1_59_1","author":"~POLJAK S.","volume-title":"Combinato- ~rial Optimization"},{"key":"e_1_2_1_60_1","author":"~REINELT G.","year":"1991","article-title":"TSPLIB--A traveling salesman problem library","journal-title":"ORSA J. Comput. 3, ~376-384.","DOI":"10.1287\/ijoc.3.4.376","doi-asserted-by":"crossref"},{"key":"e_1_2_1_62_1","unstructured":"~ROSENFELD B. 1988. A history of non-Euclidean geometry. Springer-Verlag Berlin. ~ROSENFELD B. 1988. A history of non-Euclidean geometry. Springer-Verlag Berlin."},{"key":"e_1_2_1_63_1","DOI":"10.1145\/321958.321975","doi-asserted-by":"publisher"},{"key":"e_1_2_1_64_1","unstructured":"~V^IDY^ P. M. 1989. A new algorithm for minimizing convex functions over convex sets. In ~Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE New ~York: pp. 338-343. ~V^IDY^ P. M. 1989. A new algorithm for minimizing convex functions over convex sets. In ~Proceedings of the 30th Annual Symposium on Foundations of Computer Science. IEEE New ~York: pp. 338-343."},{"key":"e_1_2_1_65_1","unstructured":"VANDENBERGHE L. AND BOYD S. 1996. Semidefinite programming. SIAM Rev. To appear. 10.1137\/1038003 VANDENBERGHE L. AND BOYD S. 1996. Semidefinite programming. SIAM Rev. To appear. 10.1137\/1038003"},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0012-365X(81)90023-6","article-title":"How well can a graph be n-colored","volume":"34","author":"VITANYI P.M.","year":"1981","journal-title":"Disc. Math."},{"key":"e_1_2_1_67_1","unstructured":"WOLKOWICZ H. 1981. Some applications of optimization in matrix theory. Lin. Algebra Appl. ~40 1 01-118. WOLKOWICZ H. 1981. Some applications of optimization in matrix theory. Lin. Algebra Appl. ~40 1 01-118.","DOI":"10.1016\/0024-3795(81)90143-9","doi-asserted-by":"crossref"},{"key":"e_1_2_1_68_1","DOI":"10.1006\/jagm.1994.1045","doi-asserted-by":"publisher"}],"container-title":["Journal of the ACM (JACM)"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/dl.acm.org\/ft_gateway.cfm?id=227684&ftid=35340&dwn=1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,16]],"date-time":"2020-02-16T15:33:54Z","timestamp":1581867234000},"score":1.0,"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,11]]},"references-count":67,"journal-issue":{"published-print":{"date-parts":[[1995,11]]},"issue":"6"},"alternative-id":["10.1145\/227683.227684"],"URL":"http:\/\/dx.doi.org\/10.1145\/227683.227684","relation":{"cites":[]},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Control and Systems Engineering","Hardware and Architecture","Software","Artificial Intelligence","Information Systems"]}}