×

zbMATH — the first resource for mathematics

Contribution of copositive formulations to the graph partitioning problem. (English) Zbl 1291.90166
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)].

MSC:
90C22 Semidefinite programming
90C27 Combinatorial optimization
65K05 Numerical mathematical programming methods
90C10 Integer programming
PDF BibTeX XML Cite
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.