Burer, Samuel; Monteiro, Renato D. C. A projected gradient algorithm for solving the maxcut SDP relaxation. (English) Zbl 1109.90341 Optim. Methods Softw. 15, No. 3-4, 175-200 (2001). Summary: In this paper, we present a projected gradient algorithm for solving the semidefinite programming (SDP) relaxation of the maximum cut (maxcut) problem. Coupled with a randomized method, this gives a very efficient approximation algorithm for the maxcut problem. We report computational results comparing our method with two earlier successful methods on problems with dimension up to 7,000. Cited in 22 Documents MSC: 90C52 Methods of reduced gradient type 90C22 Semidefinite programming 90C35 Programming involving graphs or networks Keywords:Semidefinite programming; Maxcut; Approximation algorithm; Semidefinite relaxation; Projected gradient method Software:SDPA; COL PDFBibTeX XMLCite \textit{S. Burer} and \textit{R. D. C. Monteiro}, Optim. Methods Softw. 15, No. 3--4, 175--200 (2001; Zbl 1109.90341) Full Text: DOI References: [1] DOI: 10.1137/0805002 · Zbl 0833.90087 [2] DOI: 10.1287/opre.36.3.493 · Zbl 0646.90084 [3] Benson S., SIAM Journal on Optimization (1988) [4] DOI: 10.1109/TCAD.1987.1270247 · Zbl 05447564 [5] Chen R., IEEE Transactions on Circuits and Systems 30 pp 284– (1983) · Zbl 0505.94031 [6] Fujie T., J. Global Optim. 10 pp 168– (1997) · Zbl 0881.90101 [7] Fujisawa K., High Performance Optimization pp 267– (1999) [8] Fujisawa K., Mathematical Programming 79 pp 235– (1997) · Zbl 0953.90043 [9] Goemans M. X., Journal of ACM pp 1115– (1995) · Zbl 0885.68088 [10] Golub G.H., Matrix Computations: Second edition (1989) [11] DOI: 10.1137/S1052623497328987 · Zbl 0960.65074 [12] DOI: 10.1137/0806020 · Zbl 0853.65066 [13] Karisch S.E., Solving graph bisection problems with semidefinite programming (1997) · Zbl 1040.90045 [14] Chih-Jen Lin, BIT 40 pp 536– (2000) · Zbl 0960.65033 [15] DOI: 10.1109/TIT.1979.1055985 · Zbl 0395.94021 [16] DOI: 10.1137/0801013 · Zbl 0754.90039 [17] DOI: 10.1080/10556789808805690 · Zbl 0904.90136 [18] Peinado M., Journal of Parallel and Distributed Computing 46 pp 48– (1997) [19] Pinter R.Y., J. VLSI Comput Syst 1 pp 123– (1984) [20] DOI: 10.1007/BF01100205 · Zbl 0843.90088 [21] Poljak S., Combinatorial Optimization Amer. Math, Soc pp 181– (1992) [22] Shor N. Z., Soviet Journal of Computer and Systems Science 1 pp 1, 128– (1987) [23] Ye Y., Mathematical Programming 84 pp 219– (1999) 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.