×

Computational approaches to MAX-cut. (English) Zbl 1334.90149

Anjos, Miguel F. (ed.) et al., Handbook on semidefinite, conic and polynomial optimization. New York, NY: Springer (ISBN 978-1-4614-0768-3/hbk; 978-1-4614-0769-0/ebook). International Series in Operations Research & Management Science 166, 821-847 (2012).
Summary: Max-Cut is one of the most studied combinatorial optimization problems because of its wide range of applications and because of its connections with other fields of discrete mathematics (see, e.g., the book by M. M. Deza and M. Laurent [Geometry of cuts and metrics. Berlin: Springer (1997; Zbl 0885.52001)]). Like other interesting combinatorial optimization problems, Max-Cut is very simple to state.
For the entire collection see [Zbl 1235.90002].

MSC:

90C27 Combinatorial optimization
90C22 Semidefinite programming
90-01 Introductory exposition (textbooks, tutorial papers, etc.) pertaining to operations research and mathematical programming

Citations:

Zbl 0885.52001

Software:

SDPLR; COL; Biq Mac; LOLIB
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Absil, P-A; Baker, CG; Gallivan, KA, Trust-region methods on Riemannian manifolds, Journal Foundations of Computational Mathematics, 7, 3, 303-330 (2007) · Zbl 1129.65045 · doi:10.1007/s10208-005-0179-9
[2] Anjos, MF; Wolkowicz, H., Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, Discrete Applied Mathematics, 119, 1-2, 79-106 (2002) · Zbl 1102.90369 · doi:10.1016/S0166-218X(01)00266-9
[3] Barahona, F.; Mahjoub, AR, On the cut polytope, Mathematical Programming, 36, 2, 157-173 (1986) · Zbl 0616.90058 · doi:10.1007/BF02592023
[4] Barvinok, A., Problems of distance geometry and convex properties of quadratic maps, Discrete Computational Geometry, 13, 189-202 (1995) · Zbl 0829.05025 · doi:10.1007/BF02574037
[5] Benson, SJ; Ye, Y.; Zhang, X., Solving large-scale sparse semidefinite programs for combinatorial optimization, SIAM Journal on Optimization, 10, 2, 443-461 (2000) · Zbl 0997.90059 · doi:10.1137/S1052623497328008
[6] Boros, E.; Hammer, PL; Tavares, G., Local search heuristics for quadratic unconstrained binary optimization, Journal of Heuristics, 13, 99-132 (2007) · doi:10.1007/s10732-007-9009-3
[7] Buchheim, C.; Wiegele, A.; Zheng, L., Exact algorithms for the Quadratic Linear Ordering Problem, INFORMS Journal on Computing, 22, 1, 168-177 (2010) · Zbl 1243.90168 · doi:10.1287/ijoc.1090.0318
[8] Burer, S.; Monteiro, RDC, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical Programming, 95, 2, 329-357 (2003) · Zbl 1030.90077 · doi:10.1007/s10107-002-0352-8
[9] de Klerk, E.; Pasechnik, DV; Warners, JP, On approximate graph colouring and Max-k-Cut algorithms based on the \(\vartheta \) -function, Journal of Combinatorial Optimization, 8, 3, 267-294 (2004) · Zbl 1084.68142 · doi:10.1023/B:JOCO.0000038911.67280.3f
[10] Deza, M., Laurent, M.: Geometry of Cuts and Metrics, vol. 15 of Algorithms and Combinatorics. Springer-Verlag, Berlin (1997) · Zbl 0885.52001
[11] Dolan, ED; Morè, JJ, Benchmarking optimization software with performance profile, Mathematical Programming, 91, 2, 201-213 (2001) · Zbl 1049.90004 · doi:10.1007/s101070100263
[12] Fischer, I.; Gruber, G.; Rendl, F.; Sotirov, R., Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, Mathematical Programming, 105, 451-469 (2006) · Zbl 1085.90044
[13] Frieze, A.; Jerrum, M., Improved approximation algorithms for Max k-Cut and Max Bisection, Algorithmica, 18, 1, 67-81 (1997) · Zbl 0873.68078 · doi:10.1007/BF02523688
[14] Ghaddar, B.; Anjos, MF; Liers, F., A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem, Annals of Operations Research, 188, 1, 155-174 (2011) · Zbl 1225.90144 · doi:10.1007/s10479-008-0481-4
[15] Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the Association for Computing Machinery, 42, 6, 1115-1145 (1995) · Zbl 0885.68088
[16] Grippo, L., Palagi, L., Piacentini, M., Piccialli, V.: An unconstrained approach for solving low rank SDP relaxations of { − 1, 1} quadratic problems. Technical Report 1.13, Dip. di Informatica e sistemistica A. Ruberti, Sapienza Università di Roma (2009)
[17] Grippo, L., Palagi, L., Piacentini, M., Piccialli, V., Rinaldi, G.: SpeeDP: A new algorithm to compute the SDP relaxations of Max-Cut for very large graphs. Technical Report 13.10, DII-UTOVRM - Università di Roma Tor Vergata (2010) available on Optimization Online. · Zbl 1257.90066
[18] Grippo, L.; Palagi, L.; Piccialli, V., Necessary and sufficient global optimality conditions for NLP reformulations of linear SDP problems, Journal of Global Optimization, 44, 3, 339-348 (2009) · Zbl 1180.90227 · doi:10.1007/s10898-008-9328-4
[19] Grippo, L.; Palagi, L.; Piccialli, V., An unconstrained minimization method for solving low rank SDP relaxations of the Max Cut problem, Mathematical Programming, 126, 1, 119-146 (2011) · Zbl 1206.90114 · doi:10.1007/s10107-009-0275-8
[20] Grippo, L.; Sciandrone, M., Nonmonotone globalization techniques for the Barzilai-Borwein gradient method, Computational Optimization and Applications, 23, 143-169 (2002) · Zbl 1028.90061 · doi:10.1023/A:1020587701058
[21] Grone, R.; Pierce, S.; Watkins, W., Extremal Correlation Matrices. Linear Algebra Application, 134, 63-70 (1990) · Zbl 0703.15028
[22] Grötschel, M.; Jünger, M.; Reinelt, G., Facets of the linear ordering polytope, Mathematical Programming, 33, 43-60 (1985) · Zbl 0577.05035 · doi:10.1007/BF01582010
[23] Hammer, P., Some network flow problems solved with pseudo-boolean programming, Operations Research, 13, 388-399 (1965) · Zbl 0132.13804 · doi:10.1287/opre.13.3.388
[24] Helmberg, C.; Rendl, F., Solving quadratic (0, 1)-problems by semidefinite programs and cutting planes, Mathematical Programming, 82, 3, 291-315 (1998) · Zbl 0919.90112 · doi:10.1007/BF01580072
[25] Helmberg, C.; Rendl, F., A spectral bundle method for semidefinite programming, SIAM Journal on Optimization, 10, 673-696 (2000) · Zbl 0960.65074 · doi:10.1137/S1052623497328987
[26] Hestenes, M., Multiplier and gradient methods, Journal of Optimization Theory and Application, 4, 303-320 (1969) · Zbl 0174.20705 · doi:10.1007/BF00927673
[27] Homer, S.; Peinado, M., Design and performance of parallel and distributed approximation algorithm for the Maxcut, Journal of Parallel and Distributed Computing, 46, 48-61 (1997) · doi:10.1006/jpdc.1997.1381
[28] Hungerländer, P., Rendl, F.: Semidefinite relaxations of ordering problems. Accepted for Publication in Mathematical Programming B · Zbl 1272.90046
[29] Journée, M.; Bach, F.; Absil, PA; Sepulchre, R., Low-rank optimization for semidefinite convex problems, SIAM Journal on Optimization, 20, 5, 2327-2351 (2010) · Zbl 1215.65108 · doi:10.1137/080731359
[30] Karger, D.; Motwani, R.; Sudan, M., Approximate graph colouring by semidefinite programming, Journal of the Association for Computing Machinery, 45, 246-265 (1998) · Zbl 0904.68116
[31] Lasserre, JB, An explicit equivalent positive semidefinite program for nonlinear 0-1 programs, SIAM Journal on Optimization, 12, 3, 756-769 (2002) · Zbl 1007.90046 · doi:10.1137/S1052623400380079
[32] Laurent, M., Rendl, F.: Semidefinite programming and integer programming. In: Aardal, K., Nemhauser, G.L., Weismantel, R. (eds.) Handbook in OR & MS, Discrete Optimization, vol. 12, Chap. 8. Elsevier B.V. (2005) · Zbl 1194.90066
[33] Liers, F., Jünger, M., Reinelt, G., Rinaldi, G.: Computing exact ground states of hard Ising spin glass problems by branch-and-cut. In: Hartmann, A.K., Rieger, H. (eds.) New Optimization Algorithms in Physics, pp. 47-69. Wiley-VCH Verlag (2004) · Zbl 1059.90147
[34] Lovász, L., On the Shannon capacity of a graph, IEEE Transactions on Information Theory, 25, 1, 1-7 (1979) · Zbl 0395.94021 · doi:10.1109/TIT.1979.1055985
[35] Pataki, G., On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Mathematics of Operations Research, 23, 339-358 (1998) · Zbl 0977.90051 · doi:10.1287/moor.23.2.339
[36] Poljak, S.; Rendl, F.; Wolkowicz, H., A recipe for semidefinite relaxation for 0-1 quadratic programming, Journal of Global Optimization, 7, 51-73 (1995) · Zbl 0843.90088 · doi:10.1007/BF01100205
[37] Powell, M.J.D.: A method for nonlinear constraints in minimization problem. In: Optimization, pp. 283-298. Academic Press, New York (1969) · Zbl 0194.47701
[38] Reinelt, G.: The Linear Ordering Problem: Algorithms and Applications. Heldermann Verlag (1985) · Zbl 0565.68058
[39] Rendl, F., Rinaldi, G., Wiegele, A.: Biq Mac Solver - BInary Quadratic and MAx-Cut Solver. http://biqmac.uni-klu.ac.at/.
[40] Rendl, F.; Rinaldi, G.; Wiegele, A., Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations, Mathematical Programming, 121, 2, 307-335 (2010) · Zbl 1184.90118 · doi:10.1007/s10107-008-0235-8
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.