×

Graph bisection revisited. (English) Zbl 1392.90120

Summary: The graph bisection problem is the problem of partitioning the vertex set of a graph into two sets of given sizes such that the sum of weights of edges joining these two sets is optimized. We present a semidefinite programming relaxation for the graph bisection problem with a matrix variable of order \(n\) – the number of vertices of the graph – that is equivalent to the currently strongest semidefinite programming relaxation obtained by using vector lifting. The reduction in the size of the matrix variable enables us to impose additional valid inequalities to the relaxation in order to further strengthen it. The numerical results confirm that our simplified and strengthened semidefinite relaxation provides the currently strongest bound for the graph bisection problem in reasonable time.

MSC:

90C35 Programming involving graphs or networks
90C22 Semidefinite programming

Software:

YALMIP; Mosek
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Biswas, R; Hendrickson, B; Karypis, G, Graph partitioning and parallel computing, Parallel Computing, 26, 1515-1517, (2000) · Zbl 0953.68587 · doi:10.1016/S0167-8191(00)00042-9
[2] Dai, W; Kuh, E, Simultaneous floor planning and global routing for hierarchical building-block layout, IEEE Transaction on Computer-Aided Design Integrated Circuits & Systems CAD, 6, 828-837, (1987) · doi:10.1109/TCAD.1987.1270326
[3] Klerk, E; Pasechnik, DV; Sotirov, R; Dobre, C, On semidefinite programming relaxations of maximum \(k\)-section, Mathematical Programming Series B, 136, 253-278, (2012) · Zbl 1263.90056 · doi:10.1007/s10107-012-0603-2
[4] Klerk, E; Oliveira Filho, FM; Pasechnik, DV; Anjos, M (ed.); Lasserre, J (ed.), Relaxations of combinatorial problems via association schemes, 171-200, (2012), New York · Zbl 1334.90100 · doi:10.1007/978-1-4614-0769-0_7
[5] Souza, CC; Keunings, R; Wolsey, LA; Zone, O, A new approach to minimizing the frontwidth in finite element calculations, Computer Methods in Applied Mechanics and Engineering, 111, 323-334, (1994) · Zbl 0846.73061 · doi:10.1016/0045-7825(94)90137-6
[6] Feige, U; Langberg, M, Approximation algorithms for maximization problems arising in graph partitioning, Journal of Algorithms, 41, 174-211, (2001) · Zbl 1017.68086 · doi:10.1006/jagm.2001.1183
[7] Ferreira, CE; Martin, A; Souza, CC; Weismantel, R; Wolsey, LA, The node capacitated graph partitioning problem: A computational study, Mathematical Programming, 81, 229-256, (1998) · Zbl 0919.90139
[8] Fiduccia, C. M., & Mattheyses, R. M. (1982). A linear-time heuristic for improving network partitions. In Proceedings of the 19th Design Automation Conference (pp. 175-181). · Zbl 1349.62554
[9] Garey, MR; Johnson, DS; Stockmeyer, L, Some simplified NP-complete graph problems, Theoretical Computer Science, 1, 237-267, (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1
[10] Gijswijt, D. (2005). Matrix algebras and semidefinite programming techniques for codes. PhD thesis, University of Amsterdam, The Netherlands. · Zbl 1113.90101
[11] Han, Q; Ye, Y; Zhang, J, An improved rounding method and semidefinite relaxation for graph partitioning, Mathematical Programming, 92, 509-535, (2002) · Zbl 1008.90042 · doi:10.1007/s101070100288
[12] Helmberg, C. (2004). A cutting plane algorithm for large scale semidefinite relaxations. In M. Grötschel (Ed.), Padberg Festschrift the sharpest cut (pp. 233-256). MPS-SIAM. · Zbl 1136.90431
[13] Hendrickson, B; Kolda, TG, Partitioning rectangular and structurally nonsymmetric sparse matrices for parallel processing, SIAM Journal of Scientific Computing, 21, 2048-2072, (2000) · Zbl 0960.65050 · doi:10.1137/S1064827598341475
[14] Johnson, E; Mehrotra, A; Nemhauser, G, MIN-cut clustering, Mathematical Programming, 62, 133-152, (1993) · Zbl 0807.90117 · doi:10.1007/BF01585164
[15] Karisch, SE; Rendl, F; Clausen, J, Solving graph bisection problems with semidefinite programming, INFORMS Journal on Computing, 12, 177-191, (2000) · Zbl 1040.90045 · doi:10.1287/ijoc.12.3.177.12637
[16] Lengauer, T. (1990). Combinatorial algorithms for integrated circuit layout. Chicester: Wiley. · Zbl 0709.68039
[17] Li, M., Andersen, D. G., & Smola, A. J. (2015). Graph partitioning via parallel submodular approximation to accelerate distributed machine learning. arXiv:1505.04636v1. · Zbl 0960.65050
[18] Löfberg, J. (2004). YALMIP: A toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD Conference, Taipei, Taiwan (pp. 284-289). http://users.isy.liu.se/johanl/yalmip/.
[19] MOSEK Aps. (2015). The MOSEK optimization toolbox for MATLAB manual. Version 7.1 (Revision 28) http://docs.mosek.com/7.1/toolbox/index.html. · Zbl 1008.90042
[20] Padberg, MW, The Boolean quadric polytope: some characteristics, facets and relatives, Mathematical Programming, 45, 139-172, (1989) · Zbl 0675.90056 · doi:10.1007/BF01589101
[21] Pirim, H; Ekçioğlu, B; Perkins, A; Yüceer, Ç, Clustering of high throughput gene expression data, Computers & Operations Research, 39, 3046-3061, (2012) · Zbl 1349.62554 · doi:10.1016/j.cor.2012.03.008
[22] Rendl, F., & Sotirov, R. (2016). The min-cut and vertex separator problem, Preprint. http://www.optimization-online.org/DB_FILE/2016/01/5278.pdf. · Zbl 1393.90126
[23] Rolland, E; Pirkul, H; Glover, F, Tabu search for graph partitioning, Annals of Operations Research, 63, 209-232, (1996) · Zbl 0851.90131 · doi:10.1007/BF02125455
[24] Sanchis, L, Multiple-way network partitioning, IEEE Transaction on Computers, 38, 62-81, (1989) · Zbl 0709.94615 · doi:10.1109/12.8730
[25] Simon, HD, Partitioning of unstructured problems for parallel processing, Computing Systems in Engineering, 2, 35-148, (1991) · doi:10.1016/0956-0521(91)90014-V
[26] Sotirov, R. (2012). SDP relaxations for some combinatorial optimization problems. In M. F. Anjos & J. B. Lasserre (Eds.), Handbook of semidefinite, conic and polynomial optimization: Theory, algorithms, software and applications (pp. 795-820). New York: Springer. · Zbl 1334.90116
[27] Sotirov, R, An efficient semidefinite programming relaxation for the graph partition problem, INFORMS Journal of Computers, 26, 16-30, (2014) · Zbl 1356.90104 · doi:10.1287/ijoc.1120.0542
[28] van Dam, E. R., & Sotirov, R. (2015). Semidefinite programming and eigenvalue bounds for the graph partition problem. Mathematical Programming Series B, 151(2), 379-404. · Zbl 1328.90103
[29] Wolkowicz, H; Zhao, Q, Semidefinite programming relaxations for the graph partitioning problem, Discrete Applied Mathematics, 96, 461-479, (1999) · Zbl 0932.90030 · doi:10.1016/S0166-218X(99)00102-X
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.