×

Semidefinite programming in combinatorial optimization. (English) Zbl 0887.90139

Summary: We discuss the use of semidefinite programming for combinatorial optimization problems. The main topics covered include (i) the Lovász theta function and its applications to stable sets, perfect graphs, and coding theory, (ii) the automatic generation of strong valid inequalities, (iii) the maximum cut problem and related problems, and (iv) the embedding of finite metric spaces and its relationship to the sparsest cut problem.

MSC:

90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization,SIAM Journal on Optimization 5 (1995) 13–51. · Zbl 0833.90087 · doi:10.1137/0805002
[2] F. Alizadeh, J.-P. Haeberly and M. Overton, Complementarity and nondegeneracy in semidefinite programming, Technical Report, Courant Institute of Mathematical Sciences, 1995; also in:Mathematical Programming, to appear. · Zbl 0890.90141
[3] N. Alon, Eigenvalues and expanders,Combinatorica 6 (1986) 83–96. · Zbl 0661.05053 · doi:10.1007/BF02579166
[4] N. Alon and N. Kahale, Approximating the independence number via the function, Manuscript, 1994. · Zbl 0895.90169
[5] N. Alon and V. Milman,{\(\lambda\)} 1, isoperimetric inequalities for graphs and superconcentrators,Journal of Combinatorial Theory B 38 (1985) 73–88. · Zbl 0549.05051 · doi:10.1016/0095-8956(85)90092-9
[6] Y. Aumann and Y. Rabani, An O (logk) approximate min-cut max-flow theorem and approximation algorithm,SIAM Journal on Computing, to appear. · Zbl 0910.05038
[7] E. Balas, S. Ceria and G. Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0–1 programs,Mathematical Programming 58 (1993) 295–324. · Zbl 0796.90041 · doi:10.1007/BF01581273
[8] F. Barahona and A. Mahjoub, On the cut polytope,Mathematical Programming 36 (1986) 157–173. · Zbl 0616.90058 · doi:10.1007/BF02592023
[9] A.I. Barvinok, Problems of distance geometry and convex properties of quadratic maps,Discrete and Computational Geometry 13 (1995) 189–202. · Zbl 0829.05025 · doi:10.1007/BF02574037
[10] J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space,Israel Journal of Mathematics 52 (1985) 46–52. · Zbl 0657.46013 · doi:10.1007/BF02776078
[11] A. Brouwer and W. Haemers, Association schemes, in: R. Graham, M. Grötschel and L. Lovász, eds.,Handbook of Combinatorics (North-Holland, Amsterdam, 1995) 747–771. · Zbl 0849.05072
[12] B. Chor and M. Sudan, A geometric approach to betweenness, in:Proceedings of the 3rd European Symposium on Algorithms, Lecture Notes in Computer Science, Vol. 979 (Springer, Berlin, 1995) 227–237. · Zbl 0912.68058
[13] C. Delorme and S. Poljak, Combinatorial properties and the complexity of a max-cut approximation,European Journal of Combinatorics 14 (1993) 313–333. · Zbl 0780.05040 · doi:10.1006/eujc.1993.1035
[14] C. Delorme and S. Poljak, Laplacian eigenvalues and the maximum cut problem,Mathematical Programming 62 (1993) 557–574. · Zbl 0797.90107 · doi:10.1007/BF01585184
[15] P. Delsarte, An algebraic approach to the association schemes of coding theory,Philips Research Reports, Supplement 10 (1973). · Zbl 1075.05606
[16] M. Deza and M. Laurent,Geometry of Cuts and Metrics, Algorithms and Combinatorics (Springer, Berlin, 1997). · Zbl 0885.52001
[17] U. Feige, Randomized graph products, chromatic numbers, and the Lovász-function, in:Proceedings of the 27th ACM Symposium on Theory of Computing (1995) 635–640. · Zbl 1058.94517
[18] U. Feige and M.X. Goemans, 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 Comput. and Syst. (1995) 182–189.
[19] A. Frieze and M. Jerrum, Improved approximation algorithms for MAXk-CUT and MAX BISECTION,Algorithmica 18 (1997) 67–81. · Zbl 0873.68078 · doi:10.1007/BF02523688
[20] M.X. Goemans and D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,J. ACM 42 (1995) 1115–1145; A preliminary version entitled ”.878-Approximation algorithms for MAXCUT and MAX2SAT” has appeared inProceedings 26th ACM Symposium on Theory of Computing (1994) 422–431. · Zbl 0885.68088 · doi:10.1145/227683.227684
[21] M. Golumbic,Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980). · Zbl 0541.05054
[22] M. Grötschel, L. Lovász and A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization,Combinatorica 1 (1981) 169–197. · Zbl 0492.90056 · doi:10.1007/BF02579273
[23] M. Grötschel, L. Lovász and A. Schrijver, Relaxations of vertex packing,Journal of Combinatorial Theory B 40 (1986) 330–343. · Zbl 0596.05052 · doi:10.1016/0095-8956(86)90087-0
[24] M. Grötschel, L. Lovász and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988). · Zbl 0634.05001
[25] J. Håstad, Clique is hard to approximate withinn 1–{\(\epsilon\)} , in:Proceedings of the 37th Symposium on Foundations of Computer Science (1996) 627–636.
[26] J. Håstad, Some optimal inapproximability results, in:Proceedings of the 29th ACM Symposium on Theory of Computing (1997) pp. 1–10. · Zbl 0963.68193
[27] D.S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems,SIAM Journal on Computing 11 (1982) 555–556. · Zbl 0486.68067 · doi:10.1137/0211045
[28] R. Horn and C. Johnson,Matrix Analysis (Cambridge University Press, Cambridge, 1985). · Zbl 0576.15001
[29] F. Juhász, The asymptotic behavior of Lovász’v function for random graphs,Combinatorica (1982) 153–155.
[30] D. Karger, R. Motwani and M. Sudan, Approximate graph coloring by semidefinite programming, in:Proceedings 35th of the Symposium on Foundations of Computer Science (1994) 2–13. · Zbl 0904.68116
[31] H. Karloff, How good is the Goemans-Williamson MAX CUT algorithm, in:Proceedings of the 28th ACM Symposium on Theory of Computing (1996) 427–434. · Zbl 0922.68068
[32] J. Kleinberg and M.X. Goemans, The Lovász theta function and a semidefinite programming relaxation of vertex cover,SIAM Journal on Discrete Mathematics, to appear. · Zbl 0910.90262
[33] D. Knuth, The sandwich theorem,Electronic Journal of Combinatorics 1 (1994); http://ejc.math.gatech.edu:8000/Journal/journalhome.html · Zbl 0810.05065
[34] M. Kojima, Interior-point methods for semidefinite programming,Mathematical Programming (1997) (this volume). · Zbl 0887.90156
[35] J. Lagergren and A. Russell, Vertex cover eludes the Schrijver function, Manuscript, 1997.
[36] P. Lancaster and M. Tismenetsky,The Theory of Matrices (Academic Press, Orlando, FL, 1985). · Zbl 0558.15001
[37] M. Laurent, S. Poljak and F. Rendl, Connections between the semidefinite relaxations of the max-cut and stable set problems,Mathematical Programming 77 (1997) 225–246. · Zbl 0888.90128
[38] F. Leighton and S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, in:Proceedings of the 29th Symposium on Foundations of Computer Science (1988) 422–431.
[39] A. Lewis and M. Overton, Eigenvalue optimization,Acta Numerica 5 (1996) 149–190. · Zbl 0870.65047 · doi:10.1017/S0962492900002646
[40] N. Linial, E. London and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications,Combinatorica 15 (1995) 215–246. · Zbl 0827.05021 · doi:10.1007/BF01200757
[41] L. Lovász, On the Shannon capacity of a graph,IEEE Transactions on Information Theory 25 (1979) 1–7. · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985
[42] L. Lovász, Perfect graphs, in: L. Beineke and R. Wilson, eds.,Selected Topics in Graph Theory, Vol. 2 (Academic Press, New York, 1983) 55–87. · Zbl 0536.05055
[43] L. Lovász, Combinatorial optimization: Some problems and trends, Technical Report 92–53, DIMACS, 1992.
[44] L. Lovász and A. Schrijver, Matrix cones, projection representations, and stable set polyhedra, in:Polyhedral Combinatorics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Vol. 1 (AMS, Providence, RI, 1989) 1–17. · Zbl 0745.05024
[45] L. Lovász and A. Schrijver, Cones of matrices and setfunctions, and 0–1 optimization,SIAM Journal on Optimization 1 (1991) 166–190. · Zbl 0754.90039 · doi:10.1137/0801013
[46] F. MacWilliams and N. Sloane,The Theory of Error Correcting Codes (North-Holland, Amsterdam, 1977). · Zbl 0369.94008
[47] S. Mahajan and H. Ramesh, Derandomizing semidefinite programming based approximation algorithms, in:Proceedings 36th Symposium on Foundations of Computer Science (1995) 162–169. · Zbl 0938.68915
[48] G. Malajovich, An effective version of Kronecker’s theorem on simultaneous Diophantine approximation, Technical Report, City University of Hong Kong, 1996.
[49] R. McEliece, The bounds of Delsarte and Lovász, and their applications to coding theory, in: G. Longo, ed.,Algebraic Coding Theory and Applications (Springer, Berlin, 1979) 107–178.
[50] R. McEliece, E. Rodemich, H. Rumsey and L. Welch, New upper bounds on the rate of a code via the Delsarte-McWilliams inequalities,IEEE Transactions on Information Theory 23 (1977) 157. · Zbl 0361.94016 · doi:10.1109/TIT.1977.1055688
[51] B. Mohar and S. Poljak, Eigenvalue methods in combinatorial optimization, in: R. Brualdi, S. Friedland and V. Klee, eds.,Combinatorial and Graph-Theoretic Problems in Linear Algebra, The IMA Volumes in Mathematics and its Applications, Vol. 50 (Springer, Berlin, 1993) 107–151. · Zbl 0806.90104
[52] Y. Nesterov, Quality of semidefinite relaxation for nonconvex quadratic optimization, Manuscript, 1997.
[53] Y. Nesterov and A. Nemirovskii,Interior Point Polynomial Methods in Convex Programming (SIAM, Philadelphia, PA, 1994). · Zbl 0824.90112
[54] G. Pataki, On cone-LP’s and semi-definite programs: Facial structure, basic solutions, and the simplex method, GSIA Working Paper WP 1995–03, Carnegie-Mellon University, 1995.
[55] S. Poljak, Polyhedral and eigenvalue approximations of the max-cut problem, in: G. Halász et al., eds.,Sets, Graphs, and Numbers, Colloquia Mathematica Societatis János Bolyai, Vol. 60 (North-Holland, Amsterdam, 1992) 569–581. · Zbl 0792.05102
[56] S. Poljak and F. Rendl, Nonpolyhedral relaxations of graph-bisection problems,SIAM Journal on Optimization 5 (1995) 467–487. · Zbl 0838.90130 · doi:10.1137/0805024
[57] S. Poljak and Z. Tuza, Maximum cuts and largest bipartite subgraphs, in: W. Cook, L. Lovász and P. Seymour, eds.,Combinatorial Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science (AMS, Providence, RI, 1995). · Zbl 0834.05001
[58] F. Rendl, Semidefinite programming and combinatorial optimization, Notes for a lecture series given at the University of Pisa, 1997.
[59] A. Schrijver, A comparison of the Delsarte and Lovász bounds,IEEE Transactions on Information Theory 25 (1979) 425–429. · Zbl 0444.94009 · doi:10.1109/TIT.1979.1056072
[60] C. Shannon, The zero error capacity of a channel,IRE Transactions on Information Theory 2 (1956) 8–19. · doi:10.1109/TIT.1956.1056774
[61] H. Sherali and W. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems,SIAM Journal on Discrete Mathematics 3 (1990) 411–430. · Zbl 0712.90050 · doi:10.1137/0403036
[62] A. Sinclair and M. Jerrum, Approximate counting, uniform generation and rapidly mixing markov chains,Information and Computation 82 (1989) 93–133. · Zbl 0668.05060 · doi:10.1016/0890-5401(89)90067-9
[63] M. Szegedy, A note on the theta number of Lovász and the generalized Delsarte bound, in:Proceedings of the 35th Symposium on Foundations of Computer Science (1994) 36–39.
[64] P. Tiwari, A problem that is easier to solve on the unit-cost algebraic RAM,Journal of Complexity 8 (1992) 393–397. · Zbl 0759.68039 · doi:10.1016/0885-064X(92)90003-T
[65] L. Vandenberghe and S. Boyd, Semidefinite programming,SIAM Review 38 (1996) 49–95. · Zbl 0845.65023 · doi:10.1137/1038003
[66] M. Yannakakis, Expressing combinatorial optimization problems by linear programs, in:Proceedings of the 29th Symposium on Foundations of Computer Science (1988) 223–228.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.