Semidefinite programming and eigenvalue bounds for the graph partition problem. (English) Zbl 1328.90103
Summary: The graph partition problem is the problem of partitioning the vertex set of a graph into a fixed number of sets of given sizes such that the sum of weights of edges joining different sets is optimized. In this paper we simplify a known matrix-lifting semidefinite programming relaxation of the graph partition problem for several classes of graphs and also show how to aggregate additional triangle and independent set constraints for graphs with symmetry. We present an eigenvalue bound for the graph partition problem of a strongly regular graph, extending a similar result for the equipartition problem. We also derive a linear programming bound of the graph partition problem for certain Johnson and Kneser graphs. Using what we call the Laplacian algebra of a graph, we derive an eigenvalue bound for the graph partition problem that is the first known closed form bound that is applicable to any graph, thereby extending a well-known result in spectral graph theory. Finally, we strengthen a known semidefinite programming relaxation of a specific quadratic assignment problem and the above-mentioned matrix-lifting semidefinite programming relaxation by adding two constraints that correspond to assigning two vertices of the graph to different parts of the partition. This strengthening performs well on highly symmetric graphs when other relaxations provide weak or trivial bounds.
MSC:
| 90C22 | Semidefinite programming |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C70 | Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) |
| 05E30 | Association schemes, strongly regular graphs |
Keywords:
graph partition problem; semidefinite programming; eigenvalues; strongly regular graph; symmetryReferences:
| [1] | Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 13-51 (1995) · Zbl 0833.90087 · doi:10.1137/0805002 |
| [2] | Armbruster, M., Helmberg, C., Fügenschuh, M., Martin, A.: LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison. Math. Program. Comput. 4(3), 275-306 (2012) · Zbl 1275.90053 · doi:10.1007/s12532-012-0040-5 |
| [3] | Biswas, R., Hendrickson, B., Karypis, G.: Graph partitioning and parallel computing. Parallel Comput. 26(12), 1515-1517 (2000) · Zbl 0953.68587 · doi:10.1016/S0167-8191(00)00042-9 |
| [4] | Brouwer, A.E.: Chang graphs. http://www.win.tue.nl/ aeb/graphs/Chang.html |
| [5] | Brouwer, A.E., Cohen, A.M., Neumaier, A.: Distance-Regular Graphs. Springer, Berlin (1989) · Zbl 0747.05073 · doi:10.1007/978-3-642-74341-2 |
| [6] | Brouwer, A.E., Haemers, W.H.: Spectra of Graphs, Springer, New York. http://homepages.cwi.nl/ aeb/math/ipm/ (2012) · Zbl 1231.05001 |
| [7] | Buluç, A., Meyerhenke, H., Safro, I., Sanders, P., Schulz, C.: Recent advances in graph partitioning. Preprint 2013. arXiv:1311.3144 · Zbl 0841.90120 |
| [8] | Chang, L.C.: The uniqueness and nonuniqueness of triangular association schemes. Sci. Rec. 3, 604-613 (1959) · Zbl 0089.15102 |
| [9] | Dai, W., Kuh, E.: Simultaneous floor planning and global routing for hierarchical building-block layout. IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst. 6(5), 828-837 (1987) · doi:10.1109/TCAD.1987.1270326 |
| [10] | De Klerk, E., Sotirov, R.: Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem. Math. Program. Ser. A 122(2), 225-246 (2010) · Zbl 1184.90120 · doi:10.1007/s10107-008-0246-5 |
| [11] | De Klerk, E.: Exploiting special structure in semidefinite programming: a survey of theory and applications. EJOR 201(1), 1-20 (2010) · Zbl 1177.90315 · doi:10.1016/j.ejor.2009.01.025 |
| [12] | De Klerk, E., Pasechnik, D.V., Sotirov, R., Dobre, C.: On semidefinite programming relaxations of maximum k-section. Math. Program. Ser. B 136(2), 253-278 (2012) · Zbl 1263.90056 · doi:10.1007/s10107-012-0603-2 |
| [13] | De Klerk, E., Dobre, C., Pasechnik, D.V.: Numerical block diagonalization of matrix \[*\]∗-algebras with application to semidefinite programming. Math. Program. Ser. B 129(1), 91-111 (2011) · Zbl 1225.90098 · doi:10.1007/s10107-011-0461-3 |
| [14] | De Klerk, E., Sotirov, R.: Improved semidefinite programming bounds for quadratic assignment problems with suitable symmetry. Math. Program. Ser. A 133(1), 75-91 (2012) · Zbl 1270.90045 · doi:10.1007/s10107-010-0411-5 |
| [15] | De Klerk, E., de Oliveira Filho, F.M., Pasechnik, D.V.: Relaxations of combinatorial problems via association schemes. In: Anjos, M.F., Lasserre, J.B. (eds.) Handbook of Semidefinite, Cone and Polynomial Optimization: Theory, Algorithms, Software and Applications, pp. 171-200. Springer, New York (2012) · Zbl 1334.90100 |
| [16] | De Klerk, E., Nagy, M., Sotirov, R., Truetsch, U.: Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems. EJOR 233(3), 488-499 (2014) · Zbl 1339.90203 · doi:10.1016/j.ejor.2013.10.007 |
| [17] | Delsarte, P.: An agebraic approach to the association schemes of coding theory. Philips Res. Rep. Suppl. 10 (1973) · Zbl 1075.05606 |
| [18] | Donath, W.E., Hoffman, A.J.: Lower bounds for the partitioning of graphs. IBM J. Res. Dev. 17, 420-425 (1973) · Zbl 0259.05112 · doi:10.1147/rd.175.0420 |
| [19] | Falkner, J., Rendl, F., Wolkowicz, H.: A computational study of graph partitioning. Math. Program. 66, 211-239 (1994) · Zbl 0830.90130 · doi:10.1007/BF01581147 |
| [20] | Fiduccia, C.M., Mattheyses, R.M.: A linear-time heuristic for improving network partitions. In: Proceedings of the 19th Design Automation Conference, pp. 175-181 (1982) · Zbl 0983.05078 |
| [21] | Garey, M.R., Johnson, D.S., Stockmeyer, L.: Some simplified NP-complete graph problems. Theor. Comput. Sci. 1(3), 237-267 (1976) · Zbl 0338.05120 · doi:10.1016/0304-3975(76)90059-1 |
| [22] | Gatermann, K., Parrilo, P.A.: Symmetry groups, semidefinite programs, and sum of squares. J. Pure Appl. Algebra 192, 95-128 (2004) · Zbl 1108.13021 · doi:10.1016/j.jpaa.2003.12.011 |
| [23] | Goemans, M.X., Rendl, F.: Semidefinite programs and association schemes. Computing 63(4), 331-340 (1999) · Zbl 0956.90029 |
| [24] | Haemers, W.H., Spence, E.: The pseudo-geometric graphs for generalised quadrangles of order \[(3, t)\](3,t). Eur. J. Combin. 22(6), 839-845 (2001) · Zbl 0983.05078 · doi:10.1006/eujc.2001.0507 |
| [25] | Hendrickson, B., Kolda, T.G.: Partitioning rectangular and structurally nonsymmetric sparse matrices for parallel processing. SIAM J. Sci. Comput. 21(6), 2048-2072 (2000) · Zbl 0960.65050 · doi:10.1137/S1064827598341475 |
| [26] | Higman, D.G., Sims, C.: A simple group of order 44,352,000. Math. Z. 105, 110-113 (1968) · Zbl 0186.04002 · doi:10.1007/BF01110435 |
| [27] | Juvan, M., Mohar, B.: Optimal linear labelings and eigenvalues of graphs. Discrete Appl. Math. 36, 153-168 (1992) · Zbl 0759.05087 · doi:10.1016/0166-218X(92)90229-4 |
| [28] | Karisch, S.E., Rendl, F., Clausen, J.: Solving graph bisection problems with semidefinite programming. INFORMS J. Comput. 12, 177-191 (2000) · Zbl 1040.90045 · doi:10.1287/ijoc.12.3.177.12637 |
| [29] | Karisch, SE; Rendl, F.; Pardalos, PM (ed.); Wolkowicz, H. (ed.), Semidefinite programming and graph equipartition, No. 18, 77-96 (1998), Providence · Zbl 0905.90171 |
| [30] | Karloff, H.: How good is the Goemans-Williamson max cut algorithm? SIAM J. Comput. 29(1), 336-350 (1999) · Zbl 0942.90033 · doi:10.1137/S0097539797321481 |
| [31] | Lengauer, T.: Combinatorial Algorithms for Integrated Circuit Layout. Wiley, Chicester (1990) · Zbl 0709.68039 |
| [32] | Löfberg, J.: 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/ (2004) · Zbl 0259.05112 |
| [33] | Mohar, B.; Poljak, S.; Brualdi, RA (ed.); Friedland, S. (ed.); Klee, V. (ed.), Eigenvalues in combinatorial optimization, No. 50, 107-151 (1993), Berlin · Zbl 0806.90104 |
| [34] | Pong, T.K., Sun, H., Wang, N., Wolkowicz, H.: Eigenvalue, quadratic programming, and semidefinite programming bounds for vertex separators. Technical report, University of Waterloo, Canada (2014) |
| [35] | Povh, J., Rendl, F.: Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6(3), 231-241 (2009) · Zbl 1167.90597 · doi:10.1016/j.disopt.2009.01.002 |
| [36] | Rendl, F., Sotirov, R.: Bounds for the quadratic assignment problem using the bundle method. Math. Program. Ser. B 109(2-3), 505-524 (2007) · Zbl 1278.90303 · doi:10.1007/s10107-006-0038-8 |
| [37] | Rendl, F., Wolkowicz, H.: A projection technique for partitioning nodes of a graph. Ann. Oper. Res. 58, 155-179 (1995) · Zbl 0841.90120 · doi:10.1007/BF02032130 |
| [38] | Rendl, F., Lisser, A., Piacentini, M.: Bandwidth, vertex separators and eigenvalue optimization. In: Bezdek, K., et al. (eds.) Discrete Geometry and Optimization, volume 69 of Fields Institute for Research in Mathematical Sciences, Communication Series, pp. 249-263. Springer, Berlin (2013) · Zbl 1273.90149 |
| [39] | Rinaldi, G.: Rudy. http://www-user.tu-chemnitz.de/ helmberg/rudy.tar.gz (1996) · Zbl 0953.68587 |
| [40] | Sanchis, L.: Multiple-way network partitioning. IEEE Trans. Comput. 38, 62-81 (1989) · Zbl 0709.94615 · doi:10.1109/12.8730 |
| [41] | Simon, H.D.: Partitioning of unstructured problems for parallel processing. Comput. Syst. Eng. 2, 35-148 (1991) · doi:10.1016/0956-0521(91)90014-V |
| [42] | Sotirov, R.; Anjos, MF (ed.); Lasserre, JB (ed.), SDP relaxations for some combinatorial optimization problems, 795-820 (2012), New York · Zbl 1334.90116 · doi:10.1007/978-1-4614-0769-0_27 |
| [43] | Sotirov, R.: An efficient semidefinite programming relaxation for the graph partition problem. INFORMS J. Comput. 26(1), 16-30 (2014) · Zbl 1356.90104 · doi:10.1287/ijoc.1120.0542 |
| [44] | Sturm, J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12, 625-653 (1999) · Zbl 0973.90526 |
| [45] | The GAP Group: GAP—Groups, Algorithms, and Programming. Version 4.5.6. http://www.gap-system.org (2012) |
| [46] | van Dam, E.R., Sotirov, R.: On bounding the bandwidth of graphs with symmetry. INFORMS J. Comput. (to appear) · Zbl 1327.90359 |
| [47] | Wedderburn, J.H.M.: On hypercomplex numbers. Proc. Lond. Math. Soc. 6(2), 77-118 (1907) · JFM 39.0139.01 |
| [48] | Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2, 71-109 (1998) · Zbl 0904.90145 · doi:10.1023/A:1009795911987 |
| [49] | Wolkowicz, H., Zhao, Q.: Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96/97, 461-479 (1999) · Zbl 0932.90030 |
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.
