Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
Tóm tắt
Từ khóa
Tài liệu tham khảo
~ALIZADEH , F. 1995 . Interior point methods in semidefinite programming with applications to ~combinatorial optimization . SIAM J. Optimiz. 5 , 13 - 51 . ~ALIZADEH, F. 1995. Interior point methods in semidefinite programming with applications to ~combinatorial optimization. SIAM J. Optimiz. 5, 13-51.
~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 . ~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.
~BAR-YEHUDA , R. , AND EVEN , S. 1981 . A linear time approximation algorithm for the weighted ~verllex cover problem . J. Algorithms 2 , 198 - 203 . ~BAR-YEHUDA, R., AND EVEN, S. 1981. A linear time approximation algorithm for the weighted ~verllex cover problem. J. Algorithms 2, 198-203.
~BARV ! NOK , A. I. 1995 . Problems of distance geometry and convex properties of quadratic ~maps . Disc. Computat. Geom. 13 , 189 - 202 . ~BARV!NOK, A. I. 1995. Problems of distance geometry and convex properties of quadratic ~maps. Disc. Computat. Geom. 13, 189-202.
~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 . ~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.
~BERGER M. 1987. Geometry II. Springer-Verlag Berlin. ~BERGER M. 1987. Geometry II. Springer-Verlag Berlin.
~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.
~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.
~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 . ~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.
~CHRISTENSEN , J. , AND VESTERSTROM , J. 1979 . A note on extreme positive definite matrices. ~Math . Annalen , 244 : 65 - 68 . ~CHRISTENSEN, J., AND VESTERSTROM, J. 1979. A note on extreme positive definite matrices. ~Math. Annalen, 244:65-68.
~EULER L. 1781. De mensura angulorum solidorum. Petersburg. ~EULER L. 1781. De mensura angulorum solidorum. Petersburg.
~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 . ~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.
~FE m E, 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 . 10.1145/129712.129783 ~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. 10.1145/129712.129783
~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.
~GAREY , M. , JOHNSON , D. , AND STOCKMEYER , L. 1976 . Some simplified NP-complete graph ~problems . Theoret. Comput. Sci. 1 , 237 - 267 . ~GAREY, M., JOHNSON, D., AND STOCKMEYER, L. 1976. Some simplified NP-complete graph ~problems. Theoret. Comput. Sci. 1, 237-267.
~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.
~GOEMANS , M. X. , AND WILLIAMSON , D. P. 1994 a. . 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 . 10.1145/195058.195216 ~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. 10.1145/195058.195216
~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.
~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.
~GR tSTS CHEL , M., LOV /~ SZ, L ., AND SCHRIJVER , A. 1981 . The ellipsoid method and its conse- ~quenLces in combinatorial optimization . Combinatorica 1 , 169 - 197 . ~GRtSTSCHEL, M., LOV/~SZ, L., AND SCHRIJVER, A. 1981. The ellipsoid method and its conse- ~quenLces in combinatorial optimization. Combinatorica 1, 169-197.
~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.
~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.
~HAGLIN , D.J. 1992 . Approximating maximum 2-CNF satisfiability . Paral. Proc. Lett. 2 , 181 - 187 . ~HAGLIN, D.J. 1992. Approximating maximum 2-CNF satisfiability. Paral. Proc. Lett. 2, 181-187.
~HOCHBAUM , D. S. 1982 . Approximation algorithms for the set covering and vertex cover ~problems . SIAM J. Comput. 11 , 555 - 556 . ~HOCHBAUM, D. S. 1982. Approximation algorithms for the set covering and vertex cover ~problems. SIAM J. Comput. 11, 555-556.
~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.
~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.
~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 . ~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.
~K 2 XRP , 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 . ~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.
~KNUTH , D.E. 1981. Seminumerical Algorithms . Vol. 2 of The Art of Computer Programming . ~Addison-Wesley, Reading , Mass . ~KNUTH, D.E. 1981. Seminumerical Algorithms. Vol. 2 of The Art of Computer Programming. ~Addison-Wesley, Reading, Mass.
~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.
~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
~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
~LOEWY , R. 1980 . Extreme points of a convex subset of the cone of positive definite matrices. ~Math . Annalen. 253 , 227 - 232 . ~LOEWY, R. 1980. Extreme points of a convex subset of the cone of positive definite matrices. ~Math. Annalen. 253, 227-232.
~L ovAsz, L. 1979 . On the Shannon capacity of a graph . IEEE Trans. Inf. Theory IT-25 , 1 - 7 . ~LovAsz, L. 1979. On the Shannon capacity of a graph. IEEE Trans. Inf. Theory IT-25, 1-7.
~L ovAsz, L. 1983 . Self-dual polytopes and the chromatic number of distance graphs on the ~sphere. Acta Sci . Math. 45 , 317 - 323 . ~LovAsz, L. 1983. Self-dual polytopes and the chromatic number of distance graphs on the ~sphere. Acta Sci. Math. 45, 317-323.
~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.
~L ov J. 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. ~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.
~L ov/sz, L., AND SCHRIJVER , m. 1990 . Cones of matrices and setfunctions, and 0-1 optimiza- ~tion . SIAM J. Optimiz. I , 166 - 190 . ~Lov/sz, L., AND SCHRIJVER, m. 1990. Cones of matrices and setfunctions, and 0-1 optimiza- ~tion. SIAM J. Optimiz. I, 166-190.
~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 . ~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.
~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. ~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.
~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.
~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.
~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.
~PAPADIM tT RIOU , C. H., AND YANNAKAKIS , M. 1991 . Optimization, approximation, and complex- ~ity classes . J. Comput. Syst. Sci. 43 , 425 - 440 . ~PAPADIMtTRIOU, C. H., AND YANNAKAKIS, M. 1991. Optimization, approximation, and complex- ~ity classes. J. Comput. Syst. Sci. 43, 425-440.
~PATAKI , G. 1994. On the multiplicity of optimal eigenvalues. Management Science Research ~ R eport MSRR-604, GSIA. Carnegie-Mellon Univ. , Pittsburgh, Pa . ~PATAKI, G. 1994. On the multiplicity of optimal eigenvalues. Management Science Research ~Report MSRR-604, GSIA. 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. ~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.
~POLJAK , S. , AND RENDL , F. 1994 . Node and edge relaxations of the max-cut problem . Comput- ~ing 2 ;2, 123 - 137 . ~POLJAK, S., AND RENDL, F. 1994. Node and edge relaxations of the max-cut problem. Comput- ~ing 2;2, 123-137.
~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.
~POLJAK , S. , AND TURZ i K, D . 1982 . A polynomial algorithm for constructing a large bipartite ~subgraph, with an application to a satisfiability problem . Can. J. Math. 34 , 519 - 524 . ~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.
~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. ~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.
~REINELT , G. 1991 . TSPLIB--A traveling salesman problem library . ORSA J. Comput. 3, ~376-384. ~REINELT, G. 1991. TSPLIB--A traveling salesman problem library. ORSA J. Comput. 3, ~376-384.
~ROSENFELD , B. 1988. A history of non-Euclidean geometry . Springer-Verlag , Berlin . ~ROSENFELD, B. 1988. A history of non-Euclidean geometry. Springer-Verlag, Berlin.
~V ^ID Y^, 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.
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
VITANYI , P.M. 1981 . How well can a graph be n-colored ? Disc. Math. 34 , 69 - 80 . VITANYI, P.M. 1981. How well can a graph be n-colored? Disc. Math. 34, 69-80.
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.