Povh, Janez Contribution of copositive formulations to the graph partitioning problem. (English) Zbl 1291.90166 Optimization 62, No. 1, 71-83 (2013). Summary: This article provides analysis of several copositive formulations of the graph partitioning problem and semidefinite relaxations based on them. We prove that the copositive formulations based on results from S. Burer [Math. Program. 120, No. 2 (A), 479–495 (2009; Zbl 1180.90234)] and the author [J. Glob. Optim. 48, No. 3, 447–463 (2010; Zbl 1203.90121)] are equivalent and that they both imply semidefinite relaxations which are stronger than the Donath-Hoffman eigenvalue lower bound [W. E. Donath and A. J. Hoffman, IBM J. Res. Dev. 17, 420–425 (1973; Zbl 0259.05112)] and the projected semidefinite lower bound from H. Wolkowicz and Q. Zhao [Discrete Appl. Math. 96–97, 461–479 (1999; Zbl 0932.90030)]. Cited in 1 Document MSC: 90C22 Semidefinite programming 90C27 Combinatorial optimization 65K05 Numerical mathematical programming methods 90C10 Integer programming Keywords:graph partitioning problem; copositive programming; semidefinite relaxation PDF BibTeX XML Cite \textit{J. Povh}, Optimization 62, No. 1, 71--83 (2013; Zbl 1291.90166) Full Text: DOI References: [1] DOI: 10.1016/0167-9260(95)00008-4 · Zbl 0876.94063 · doi:10.1016/0167-9260(95)00008-4 [2] DOI: 10.1006/jcss.1998.1605 · Zbl 0937.68160 · doi:10.1006/jcss.1998.1605 [3] DOI: 10.1023/A:1026583532263 · doi:10.1023/A:1026583532263 [4] I. Bomze, F. Jarre, and F. Rendl.Quadratic factorization heuristics for copositive programming,Math. Programm. Comput. 3, (2009), 37–57 · Zbl 1219.90134 · doi:10.1007/s12532-011-0022-z [5] DOI: 10.1137/070711815 · Zbl 1187.90187 · doi:10.1137/070711815 [6] DOI: 10.1007/s10107-008-0223-z · Zbl 1180.90234 · doi:10.1007/s10107-008-0223-z [7] DOI: 10.1137/S1052623401383248 · Zbl 1035.90058 · doi:10.1137/S1052623401383248 [8] DOI: 10.1147/rd.175.0420 · Zbl 0259.05112 · doi:10.1147/rd.175.0420 [9] M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, New York, 1979 · Zbl 0411.68039 [10] DOI: 10.1007/s004530010013 · Zbl 0951.68178 · doi:10.1007/s004530010013 [11] Horn RA, Matrix Analysis (1990) [12] S.E. Karisch and F. Rendl, Semidefinite programming and graph equipartition, inTopics in Semidefinite and Interior-Point methods (Toronto, ON, 1996), Vol. 18, Fields Institude Communication, American Mathematical Society, Providence, RI, 1998, pp. 77–95 · Zbl 0905.90171 [13] DOI: 10.1007/s10107-002-0342-x · Zbl 1030.90079 · doi:10.1007/s10107-002-0342-x [14] DOI: 10.1007/BF02592948 · Zbl 0637.90078 · doi:10.1007/BF02592948 [15] Povh J, Towards the Optimum by Semidefinite and Copositive Programming (2009) [16] DOI: 10.1007/s10898-009-9499-7 · Zbl 1203.90121 · doi:10.1007/s10898-009-9499-7 [17] DOI: 10.1137/050637467 · Zbl 1143.90025 · doi:10.1137/050637467 [18] DOI: 10.1016/j.disopt.2009.01.002 · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002 [19] DOI: 10.1016/S0166-218X(99)00102-X · Zbl 0932.90030 · doi:10.1016/S0166-218X(99)00102-X [20] DOI: 10.1023/A:1009795911987 · Zbl 0904.90145 · doi:10.1023/A:1009795911987 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.