Michel X. Goemans
David P. Williamson
- ~ALIZADEH, F. 1995. Interior point methods in semidefinite programming with applications to ~combinatorial optimization. SIAM J. Optimiz. 5, 13-51.Google Scholar
- ~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
- ~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
- ~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. Google Scholar
- ~BARV!NOK, A. I. 1995. Problems of distance geometry and convex properties of quadratic ~maps. Disc. Computat. Geom. 13, 189-202.Google Scholar
- ~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. Google Scholar
- ~BERGER, M. 1987. Geometry II. Springer-Verlag, Berlin.Google Scholar
- ~BONDY, J. A., AND MURTY, U. S.R. 1976. Graph Theory with Applications. American Elsevier ~Publishing, New York, N.Y. Google Scholar
- ~BOYD, S., EL GHAOUI, L., FERON, E., AND BALAKRISHNAN, V. 1994. Linear Matrix Inequalities in ~System and Control Theory. SIAM, Philadelphia, Pa.Google Scholar
- ~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. Google Scholar
- ~CHRISTENSEN, J., AND VESTERSTROM, J. 1979. A note on extreme positive definite matrices. ~Math. Annalen, 244:65-68.Google Scholar
- ~DELORME, C., AND POLIAK, S. 1993a. Combinatorial properties and the complexity of a ~max-cut approximation. Europ. J. Combinat. 14, 313-333. Google Scholar
- ~DELORME, C., AND POLJAK, S. 1993b. Laplacian eigenvalues and the maximum cut problem. ~Math. Prog. 62, 557-574. Google Scholar
- ~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. Google Scholar
- ~EULER, L. 1781. De mensura angulorum solidorum. Petersburg.Google Scholar
- ~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. Google Scholar
- ~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. Google Scholar
- ~FRIEZE, A., AND JERRUM, M. 1996. Improved approximation algorithms for MAX k-CUT and ~MAX BISECTION. Algorithmica, to appear.Google Scholar
- ~GAREY, M., JOHNSON, D., AND STOCKMEYER, L. 1976. Some simplified NP-complete graph ~problems. Theoret. Comput. Sci. 1, 237-267.Google Scholar
- ~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
- ~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. Google Scholar
- ~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. Google Scholar
- ~GOLUB, G. H., AND VAN LOAN, C.F. 1983. Matrix Computations. The Johns Hopkins Uniw:r- ~sity Press, Baltimore, Md.Google Scholar
- ~GRONE, R., PIERCE, S., AND WATKINS, W. 1990. Extremal correlation matrices. Lin. Algebra ~Appl. 134, 63-70.Google Scholar
- ~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
- ~GR~STSCHEL, M., LOVXSZ, L., AND SCHRIJVER, A. 1988. Geometric Algorithms and Combinatorial ~Optimization. Springer-Verlag, Berlin.Google Scholar
- ~HADLOCK, F. 1975. Finding a maximum cut of a planar graph in polynomial time. SIAM J. ~Comput. 4, 221-225.Google Scholar
- ~HAGLIN, D.J. 1992. Approximating maximum 2-CNF satisfiability. Paral. Proc. Lett. 2, 181-187.Google Scholar
- ~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. Google Scholar
- ~HOCHBAUM, D. S. 1982. Approximation algorithms for the set covering and vertex cover ~problems. SIAM J. Comput. 11, 555-556.Google Scholar
- ~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. Google Scholar
- ~HOMER, S., AND PEINAr)O, M. A highly parallel implementation of the Goemans/Williamson ~algorithm to approximate MaxCut. Manuscript.Google Scholar
- ~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
- ~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
- ~KNUTH, D.E. 1981. Seminumerical Algorithms. Vol. 2 of The Art of Computer Programming. ~Addison-Wesley, Reading, Mass. Google Scholar
- ~LANCASTER, P., AND TISMENETSKY, M. 1985. The Theory of Matrices. Academic Press, Orlando, ~Fla.Google Scholar
- ~LAURENT, M., AND POLJAK, S. 1996. On the facial structure of the set of correlation matrices. ~SIAM J. Matrix Anal., and Appl. to appear. Google Scholar
- ~LI, C.-K., AND TAM, B.-S. 1994. A note on extreme correlation matrices. SIAM J. Matrix Anal. ~and Appl. J5, 903-908. Google Scholar
- ~LOEWY, R. 1980. Extreme points of a convex subset of the cone of positive definite matrices. ~Math. Annalen. 253, 227-232.Google Scholar
- ~LovAsz, L. 1979. On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT-25, 1-7.Google Scholar
- ~LovAsz, L. 1983. Self-dual polytopes and the chromatic number of distance graphs on the ~sphere. Acta Sci. Math. 45, 317-323.Google Scholar
- ~LovAsz, L. 1992. Combinatorial optimization: Some problems and trends. DIMACS Technical ~Report 92-53.Google Scholar
- ~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
- ~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
- ~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. Google Scholar
- ~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
- ~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
- ~NESTEROV, ~., AND NEMIROVSKII, A. 1994. Interior Point Polynomial Methods in Convex ?ro- ~gramming. Society for Industrial and Applied Mathematics, Philadelphia, Pa.Google Scholar
- ~ORLOVA, G. I., AND DORFMAN, Y.G. 1972. Finding the maximal cut in a graph. Eng. Cyber. 10, ~502-506.Google Scholar
- ~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. Google Scholar
- ~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. Google Scholar
- ~PAPADIMtTRIOU, C. H., AND YANNAKAKIS, M. 1991. Optimization, approximation, and complex- ~ity classes. J. Comput. Syst. Sci. 43, 425-440.Google Scholar
- ~PATAKI, G. 1994. On the multiplicity of optimal eigenvalues. Management Science Research ~Report MSRR-604, GSIA. Carnegie-Mellon Univ., Pittsburgh, Pa.Google Scholar
- ~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
- ~POLJAK, S., AND RENDL, F. 1994. Node and edge relaxations of the max-cut problem. Comput- ~ing 2;2, 123-137.Google Scholar
- ~POLJAK, S., AND RENDL, F. 1995a. Nonpolyhedral relaxations of graph-bisection problems. ~SIAM J. Optim., to appear.Google Scholar
- ~POLJAK, S., AND RENDL, F. 1995b. Solving the max-cut problem using eigenvalues. Disc. Appl. ~Math. 62, 249-278. Google Scholar
- ~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
- ~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
- ~REINELT, G. 1991. TSPLIB--A traveling salesman problem library. ORSA J. Comput. 3, ~376-384.Google Scholar
- ~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
- ~ROSENFELD, B. 1988. A history of non-Euclidean geometry. Springer-Verlag, Berlin.Google Scholar
- ~SAHNI, S., AND GONZALEZ, T. 1976. P-complete approximation problems. J. ACM 23, 3 (July), ~555-565. Google Scholar
- ~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
- VANDENBERGHE, L., AND BOYD, S. 1996. Semidefinite programming. SIAM Rev. To appear. Google Scholar
- VITANYI, P.M. 1981. How well can a graph be n-colored? Disc. Math. 34, 69-80.Google Scholar
- WOLKOWICZ, H. 1981. Some applications of optimization in matrix theory. Lin. Algebra Appl. ~40, 1,01-118.Google Scholar
- ~YANNA~,~KIS, M. 1994. On the approximation of maximum satisfiability. J. Algorithms 17, ~475-:502. Google Scholar
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