article

Free access

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Authors:

Michel X. Goemans,

David P. WilliamsonAuthors Info & Claims

Journal of the ACM (JACM), Volume 42, Issue 6

Pages 1115 - 1145

https://doi.org/10.1145/227683.227684

Published: 01 November 1995 Publication History

PDF eReader

References

[1]

~ALIZADEH, F. 1995. Interior point methods in semidefinite programming with applications to ~combinatorial optimization. SIAM J. Optimiz. 5, 13-51.

Google Scholar

[2]

~ARORA, S., LUND, C., MOTWANI, R., SUDAN, M., AND SZEGEDY, M. 1992. Proof verification and ~hardness of approximation problems. In Proceedings of the 33rd Annual Symposium on Founda- ~tions of Computer Science. IEEE, New York, pp. 14-23.

Google Scholar

[3]

~BAR-YEHUDA, R., AND EVEN, S. 1981. A linear time approximation algorithm for the weighted ~verllex cover problem. J. Algorithms 2, 198-203.

Google Scholar

[4]

~BARAHONA, F., GRtSTSCHEL, M., JUNGER, M., AND REINELT, G. 1988. An application of combi-natorial optimization to statistical physics and circuit layout design. Oper. Res. 36, 493-513.

Crossref

Google Scholar

[5]

~BARV!NOK, A. I. 1995. Problems of distance geometry and convex properties of quadratic ~maps. Disc. Computat. Geom. 13, 189-202.

Google Scholar

[6]

~BELLARE, M., GOLDREICH, O., AND SUDAN, M. 1995. Free bits, PCP and non-approximability-- ~Towards tight results. In Proceedings of the 36th Annual Symposium on Foundations of Computer ~Science. IEEE, Los Alamitos, Calif., pp. 422-431.

Crossref

Google Scholar

[7]

~BERGER, M. 1987. Geometry II. Springer-Verlag, Berlin.

Google Scholar

[8]

~BONDY, J. A., AND MURTY, U. S.R. 1976. Graph Theory with Applications. American Elsevier ~Publishing, New York, N.Y.

Crossref

Google Scholar

[9]

~BOYD, S., EL GHAOUI, L., FERON, E., AND BALAKRISHNAN, V. 1994. Linear Matrix Inequalities in ~System and Control Theory. SIAM, Philadelphia, Pa.

Google Scholar

[10]

~CHOR, B., AND SUDAN, m. 1995. A geometric approach to betweenness. In Algorithms-ESA '95, ~P. Spirakis, ed. Lecture Notes in Computer Science, vol. 979. Springer-Verlag, New York, ~pp. 227-237.

Crossref

Google Scholar

[11]

~CHRISTENSEN, J., AND VESTERSTROM, J. 1979. A note on extreme positive definite matrices. ~Math. Annalen, 244:65-68.

Google Scholar

[12]

~DELORME, C., AND POLIAK, S. 1993a. Combinatorial properties and the complexity of a ~max-cut approximation. Europ. J. Combinat. 14, 313-333.

Crossref

Google Scholar

[13]

~DELORME, C., AND POLJAK, S. 1993b. Laplacian eigenvalues and the maximum cut problem. ~Math. Prog. 62, 557-574.

Crossref

Google Scholar

[14]

~DELORME, C., AND POLJAK, S. 1993c. The performance of an eigenvalue bound on the max-cut ~problem in some classes of graphs. Disc. Math. 111, 145-156.

Crossref

Google Scholar

[15]

~EULER, L. 1781. De mensura angulorum solidorum. Petersburg.

Google Scholar

[16]

~FEIGE,. U., AND GOEMANS, M.X. 1995. Approximating the value of two prover proof systems, ~with applications to MAX 2SAT and MAX DICUT. In Proceedings of the 3rd Israel Symposium ~on Theory of Computing and Systems. IEEE Computer Society Press, Los Alamitos, Calif., ~pp. 182-189.

Crossref

Google Scholar

[17]

~FEmE, U., AND LOVJ. SZ, L. 1992. Two-prover one-round proof systems: Their power and their ~problems. In Proceedings of the 24th Annual ACM Symposium on the Theory of Computing ~(Victoria, S.C., Canada, May 4-6). ACM, New York, pp. 733-744.

Crossref

Google Scholar

[18]

~FRIEZE, A., AND JERRUM, M. 1996. Improved approximation algorithms for MAX k-CUT and ~MAX BISECTION. Algorithmica, to appear.

Google Scholar

[19]

~GAREY, M., JOHNSON, D., AND STOCKMEYER, L. 1976. Some simplified NP-complete graph ~problems. Theoret. Comput. Sci. 1, 237-267.

Google Scholar

[20]

~GIRARD, A. 1629. De la mesure de la superficie des triangles et polygones sph6riques. Appendix ~to "Invention nouvelle en l'alg~bre". Amsterdam.

Google Scholar

[21]

~GOEMANS, M. X., AND WILLIAMSON, D. P. 1994a. .878-approximation algorithms for MAX ~CUT and MAX 2SAT. In Proceedings of the 26th Annual ACM Symposium on the Theory of ~Computing (Montreal, Que., Canada, May 23-25). ACM, New York, pp. 422-431.

Crossref

Google Scholar

[22]

~GOEM,~'~S, M. X., AND WILLIAMSON, D.P. 1994b. New 3/4-approximation algorithms for the ~maximum satisfiability problem. SIAM J. Disc. Math. 7, 656-666.

Crossref

Google Scholar

[23]

~GOLUB, G. H., AND VAN LOAN, C.F. 1983. Matrix Computations. The Johns Hopkins Uniw:r- ~sity Press, Baltimore, Md.

Google Scholar

[24]

~GRONE, R., PIERCE, S., AND WATKINS, W. 1990. Extremal correlation matrices. Lin. Algebra ~Appl. 134, 63-70.

Google Scholar

[25]

~GRtSTSCHEL, M., LOV/~SZ, L., AND SCHRIJVER, A. 1981. The ellipsoid method and its conse- ~quenLces in combinatorial optimization. Combinatorica 1, 169-197.

Google Scholar

[26]

~GR~STSCHEL, M., LOVXSZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial ~Optimization. Springer-Verlag, Berlin.

Google Scholar

[27]

~HADLOCK, F. 1975. Finding a maximum cut of a planar graph in polynomial time. SIAM J. ~Comput. 4, 221-225.

Google Scholar

[28]

~HAGLIN, D.J. 1992. Approximating maximum 2-CNF satisfiability. Paral. Proc. Lett. 2, 181-187.

Google Scholar

[29]

~HAGLIN, D. J., AND VENKATESAN, S. M: 1991. Approximation and intractability results for the ~maximum cut problem and its variants. IEEE Trans. Comput. 40, 110-113.

Crossref

Google Scholar

[30]

~HOCHBAUM, D. S. 1982. Approximation algorithms for the set covering and vertex cover ~problems. SIAM J. Comput. 11, 555-556.

Google Scholar

[31]

~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.

Crossref

Google Scholar

[32]

~HOMER, S., AND PEINAr)O, M. A highly parallel implementation of the Goemans/Williamson ~algorithm to approximate MaxCut. Manuscript.

Google Scholar

[33]

~KARGER, D., MOTWANI, R., AND SUDAN, M. 1994. Approximate graph coloring by semidefinite ~programming. In Proceedings of the 35th Annual Symposium on Foundations of Computer ~Science. IEEE, New York, pp. 2-13.

Google Scholar

[34]

~K2XRP, R. M. 1972. Reducibility among combinatorial problems. In Complexity of Computer ~Computations, R. Miller and J. Thatcher, eds. Plenum Press, New York, pp. 85-103.

Google Scholar

[35]

~KNUTH, D.E. 1981. Seminumerical Algorithms. Vol. 2 of The Art of Computer Programming. ~Addison-Wesley, Reading, Mass.

Crossref

Google Scholar

[36]

~LANCASTER, P., AND TISMENETSKY, M. 1985. The Theory of Matrices. Academic Press, Orlando, ~Fla.

Google Scholar

[37]

~LAURENT, M., AND POLJAK, S. 1996. On the facial structure of the set of correlation matrices. ~SIAM J. Matrix Anal., and Appl. to appear.

Crossref

Google Scholar

[38]

~LI, C.-K., AND TAM, B.-S. 1994. A note on extreme correlation matrices. SIAM J. Matrix Anal. ~and Appl. J5, 903-908.

Crossref

Google Scholar

[39]

~LOEWY, R. 1980. Extreme points of a convex subset of the cone of positive definite matrices. ~Math. Annalen. 253, 227-232.

Google Scholar

[40]

~LovAsz, L. 1979. On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT-25, 1-7.

Google Scholar

[41]

~LovAsz, L. 1983. Self-dual polytopes and the chromatic number of distance graphs on the ~sphere. Acta Sci. Math. 45, 317-323.

Google Scholar

[42]

~LovAsz, L. 1992. Combinatorial optimization: Some problems and trends. DIMACS Technical ~Report 92-53.

Google Scholar

[43]

~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.

Google Scholar

[44]

~Lov/sz, L., AND SCHRIJVER, m. 1990. Cones of matrices and setfunctions, and 0-1 optimiza- ~tion. SIAM J. Optimiz. I, 166-190.

Google Scholar

[45]

~MAHAJAN, S., AND RAMESH, H. 1995. Derandomizing semidefinite programming based approxi- ~mation algorithms. In Proceedings of the 36th Annual Symposium on Foundations of Computer ~Science. IEEE, Los Alamitos, Calif., pp. 162-163.

Crossref

Google Scholar

[46]

~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.

Google Scholar

[47]

~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.

Google Scholar

[48]

~NESTEROV, ~., AND NEMIROVSKII, A. 1994. Interior Point Polynomial Methods in Convex ?ro- ~gramming. Society for Industrial and Applied Mathematics, Philadelphia, Pa.

Google Scholar

[49]

~ORLOVA, G. I., AND DORFMAN, Y.G. 1972. Finding the maximal cut in a graph. Eng. Cyber. 10, ~502-506.

Google Scholar

[50]

~OVERTON, M. L., AND WOMERSLEY, R.S. 1992. On the sum of the largest eigenvalues of a ~symmetric matrix. SIAM J. Matrix Anal. and Appl. 13, 41-45.

Crossref

Google Scholar

[51]

~OVERTON, M. L., AND WOMERSLEY, R.S. 1993. Optimality conditions and duality theory for ~minimizing sums of the largest eigenvalues of symmetric matrices. Math. Prog. 62, 321-357.

Crossref

Google Scholar

[52]

~PAPADIMtTRIOU, C. H., AND YANNAKAKIS, M. 1991. Optimization, approximation, and complex- ~ity classes. J. Comput. Syst. Sci. 43, 425-440.

Google Scholar

[53]

~PATAKI, G. 1994. On the multiplicity of optimal eigenvalues. Management Science Research ~Report MSRR-604, GSIA. Carnegie-Mellon Univ., Pittsburgh, Pa.

Google Scholar

[54]

~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.

Google Scholar

[55]

~POLJAK, S., AND RENDL, F. 1994. Node and edge relaxations of the max-cut problem. Comput- ~ing 2;2, 123-137.

Google Scholar

[56]

~POLJAK, S., AND RENDL, F. 1995a. Nonpolyhedral relaxations of graph-bisection problems. ~SIAM J. Optim., to appear.

Google Scholar

[57]

~POLJAK, S., AND RENDL, F. 1995b. Solving the max-cut problem using eigenvalues. Disc. Appl. ~Math. 62, 249-278.

Crossref

Google Scholar

[58]

~POLJAK, S., AND TURZiK, D. 1982. A polynomial algorithm for constructing a large bipartite ~subgraph, with an application to a satisfiability problem. Can. J. Math. 34, 519-524.

Google Scholar

[59]

~POLJAK, S., AND Tuz^, Z. 1995. Maximum cuts and largest bipartite subgraphs. In Combinato- ~rial Optimization. W. Cook, L. Lovfisz, and P. Seymour, eds. DIMACS series in Discrete ~Mathematics and Theoretical Computer Science, Vol. 20. American Mathematical Society, ~Providence, R.1. To be published.

Google Scholar

[60]

~REINELT, G. 1991. TSPLIB--A traveling salesman problem library. ORSA J. Comput. 3, ~376-384.

Google Scholar

[61]

~RENDL, F., VANDERBEI, R., AND WOLKOWICZ, n. 1993. Interior point methods for max-rain ~eigenvalue problems. Report 264, Technische Universitiit Graz, Graz, Austria.

Google Scholar

[62]

~ROSENFELD, B. 1988. A history of non-Euclidean geometry. Springer-Verlag, Berlin.

Google Scholar

[63]

~SAHNI, S., AND GONZALEZ, T. 1976. P-complete approximation problems. J. ACM 23, 3 (July), ~555-565.

Crossref

Google Scholar

[64]

~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.

Google Scholar

[65]

VANDENBERGHE, L., AND BOYD, S. 1996. Semidefinite programming. SIAM Rev. To appear.

Crossref

Google Scholar

[66]

VITANYI, P.M. 1981. How well can a graph be n-colored? Disc. Math. 34, 69-80.

Google Scholar

[67]

WOLKOWICZ, H. 1981. Some applications of optimization in matrix theory. Lin. Algebra Appl. ~40, 1,01-118.

Google Scholar

[68]

~YANNA~,~KIS, M. 1994. On the approximation of maximum satisfiability. J. Algorithms 17, ~475-:502.

Crossref

Google Scholar

Cited By

View all

Xin FZhang MLi JLuo C(2024)Phase Retrieval for Radar Constant–Modulus Signal Design Based on the Bacterial Foraging Optimization AlgorithmElectronics10.3390/electronics1303050613:3(506)Online publication date: 25-Jan-2024
https://doi.org/10.3390/electronics13030506
Zhao ARubin N(2024)Expanding the reach of quantum optimization with fermionic embeddingsQuantum10.22331/q-2024-08-28-14518(1451)Online publication date: 28-Aug-2024
https://doi.org/10.22331/q-2024-08-28-1451
Patel DColes PWilde M(2024)Variational Quantum Algorithms for Semidefinite ProgrammingQuantum10.22331/q-2024-06-17-13748(1374)Online publication date: 17-Jun-2024
https://doi.org/10.22331/q-2024-06-17-1374
Show More Cited By

Index Terms

Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming

Recommendations

An improved semidefinite programming relaxation for the satisfiability problem

The satisfiability (SAT) problem is a central problem in mathematical logic, computing theory, and artificial intelligence. An instance of SAT is specified by a set of boolean variables and a propositional formula in conjunctive normal form. Given such ...
Approximation algorithms for the maximum satisfiability problem

The maximum satisfiability problem (MAX SAT) is the following: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we present approximation algorithms for MAX SAT, ...
On Semidefinite Programming Relaxations of (2+p)-SAT

Recently, de Klerk, van Maaren and Warners [10] investigated a relaxation of 3-SAT via semidefinite programming. Thus a 3-SAT formula is relaxed to a semidefinite feasibility problem. If the feasibility problem is infeasible then a certificate of ...

Comments

Information & Contributors

Information

Published In

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1995

Published in JACM Volume 42, Issue 6

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2,405
Total Citations
View Citations
11,494
Total Downloads

Downloads (Last 12 months)1,328
Downloads (Last 6 weeks)155

Reflects downloads up to 06 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Xin FZhang MLi JLuo C(2024)Phase Retrieval for Radar Constant–Modulus Signal Design Based on the Bacterial Foraging Optimization AlgorithmElectronics10.3390/electronics1303050613:3(506)Online publication date: 25-Jan-2024
https://doi.org/10.3390/electronics13030506
Zhao ARubin N(2024)Expanding the reach of quantum optimization with fermionic embeddingsQuantum10.22331/q-2024-08-28-14518(1451)Online publication date: 28-Aug-2024
https://doi.org/10.22331/q-2024-08-28-1451
Patel DColes PWilde M(2024)Variational Quantum Algorithms for Semidefinite ProgrammingQuantum10.22331/q-2024-06-17-13748(1374)Online publication date: 17-Jun-2024
https://doi.org/10.22331/q-2024-06-17-1374
Watts AChowdhury AEpperly AHelton JKlep I(2024)Relaxations and Exact Solutions to Quantum Max Cut via the Algebraic Structure of Swap OperatorsQuantum10.22331/q-2024-05-22-13528(1352)Online publication date: 22-May-2024
https://doi.org/10.22331/q-2024-05-22-1352
Zhao J(2024)Experimental Design through an Optimization LensSSRN Electronic Journal10.2139/ssrn.4780792Online publication date: 2024
https://doi.org/10.2139/ssrn.4780792
Nishijima MNakata K(2024)GENERALIZATIONS OF DOUBLY NONNEGATIVE CONES AND THEIR COMPARISONJournal of the Operations Research Society of Japan10.15807/jorsj.67.8467:3(84-109)Online publication date: 31-Jul-2024
https://doi.org/10.15807/jorsj.67.84
Shim HKuang ZLin ZMiller O(2024)Fundamental limits to multi-functional and tunable nanophotonic responseNanophotonics10.1515/nanoph-2023-063013:12(2107-2116)Online publication date: 4-Jan-2024
https://doi.org/10.1515/nanoph-2023-0630
Zheng ZTang ZWei ZSun J(2024)Numerical investigation of effective nonlinear coefficient model for coupled third harmonic generationOptics Express10.1364/OE.51414832:5(7907)Online publication date: 20-Feb-2024
https://doi.org/10.1364/OE.514148
Tang TToh K(2024)A Feasible Method for Solving an SDP Relaxation of the Quadratic Knapsack ProblemMathematics of Operations Research10.1287/moor.2022.134549:1(19-39)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1287/moor.2022.1345
Yu QKüçükyavuz S(2024)On Constrained Mixed-Integer DR-Submodular MinimizationMathematics of Operations Research10.1287/moor.2022.0320Online publication date: 8-Apr-2024
https://doi.org/10.1287/moor.2022.0320
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

References

Cited By

Index Terms

Recommendations

An improved semidefinite programming relaxation for the satisfiability problem

Approximation algorithms for the maximum satisfiability problem

On Semidefinite Programming Relaxations of (2+p)-SAT

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations