An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem

References

• Alizadeh F (1995) Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1):13–51.Crossref, Google Scholar
• Anstreicher K, Wolkowicz H (2000) On Lagrangian relaxation of quadratic matrix constraints. SIAM. J. Matrix Anal. Appl. 22(1):41–55.Crossref, Google Scholar
• Armbruster M (2007) Branch-and-cut for a semidefinite relaxation of large-scale minimum bisection problems. Ph.D. thesis, Technische Universität Chemnitz, Germany.Google Scholar
• Armbruster M, Fügenschuh M, Helmberg C, Martin A (2012) LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: A computational comparison. Math. Programming Comput. 4(3):275–306.Crossref, Google Scholar
• Battiti R, Bertossi A (1999) Greedy, prohibition, and reactive heuristics for graph partitioning. IEEE Trans. Comput. 48(4):361–385.Crossref, Google Scholar
• Biswas R, Hendrickson B, Karypis G (2000) Graph partitioning and parallel computing. Parallel Comput. 26(12):1515–1517.Crossref, Google Scholar
• Bui TN, Moon BR (1995) Genetic algorithm and graph partitioning. IEEE Trans. Comput. 45(7):814–855.Google Scholar
• Chopra S, Rao MR (1993) The partition problem. Math. Programming 59(1/3):87–115.Crossref, Google Scholar
• Dai W, Kuh E (1987) Simultaneous floor planning and global routing for hierarchical building-block layout. IEEE Trans. Comput.-Aided Des. Integrated Circuits System 6(5):828–837.Crossref, Google Scholar
• De Klerk E, de Oliveira Filho FM, Pasechnik DV (2012a) Relaxations of combinatorial problems via association schemes. Anjos MF, Lasserre JB, eds. Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, Vol. 166 (Springer Verlag, Heidelberg), 171–200.Crossref, Google Scholar
• De Klerk E, Pasechnik DV, Sotirov R, Dobre C (2012b) On semidefinite programming relaxations of maximum k-section. Math. Programming, Ser. B 136(2):253–278.Crossref, Google Scholar
• de Souza CC, Keunings R, Wolsey LA, Zone O (1994) A new approach to minimizing the frontwidth in finite element calculations. Comput. Method Appl. M. 111(3–4):323–334.Crossref, Google Scholar
• Ding Y, Wolkowicz H (2009) A low dimensional semidefinite relaxation for the quadratic assignment problem. Math. Oper. Res. 34(4):1008–1022.Link, Google Scholar
• Ding Y, Ge D, Wolkowicz H (2011) On equivalence of semidefinite relaxations for quadratic matrix programming. Math. Oper. Res. 36(1):88–104.Link, Google Scholar
• Donath WE, Hoffman AJ (1973) Lower bounds for the partitioning of graphs. IBM J. Res. Development 17(5):420–425.Crossref, Google Scholar
• Eisenblätter A (2001) Frequency assignment in GSM networks. Ph.D. thesis, Technische Universität Berlin, Germany.Google Scholar
• Erdős P, Rényi A (1959) On random graphs. Publicationes Mathematicae 6:290–297.Crossref, Google Scholar
• Erdős P, Rényi A (1960) On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci. 5:17–61.Google Scholar
• Feige U, Langberg M (2001) Approximation algorithms for maximization problems arising in graph partitioning. J. Algorithm 41(2):174–211.Crossref, Google Scholar
• Ferreira CE, Martin A, de Souza CC, Weismantel R, Wolsey LA (1998) The node capacitated graph partitioning problem: A computational study. Math. Programming 81(2):229–256.Crossref, Google Scholar
• Fiduccia CM, Mattheyses RM (1982) A linear-time heuristic for improving network partitions. Proc. 19th Design Automation Conf. (IEEE, Piscataway, NJ), 175–181.Crossref, Google Scholar
• Frieze A, Jerrum M (1997) Improved approximation algorithms for max k-cut and max bisection. Algorithmica 18(1):67–81.Crossref, Google Scholar
• Garey MR, Johnson DS, Stockmeyer L (1976) Some simplified NP-complete graph problems. Theoret. Comput. Sci. 1(3):237–267.Crossref, Google Scholar
• Ghaddar B, Anjos MF, Liers F (2011) A branch-and-cut algorithm based on semidefinite programming for the minimum k-partition problem. Ann. Oper. Res. 188(1):155–174.Crossref, Google Scholar
• Graham A (1981) Kronecker Products and Matrix Calculus with Applications (Ellis Horwood Ltd., Chichester, UK).Google Scholar
• Han Q, Ye Y, Zhang J (2002) An improved rounding method and semidefinite relaxation for graph partitioning. Math. Programming 92:(3)509–535.Crossref, Google Scholar
• Hendrickson B, Kolda TG (2000) Partitioning rectangular and structurally nonsymmetric sparse matrices for parallel processing. SIAM J. Sci. Comput. 21(6):2048–2072.Crossref, Google Scholar
• Helmberg C (2004) A cutting plane algorithm for large scale semidefinite relaxations. Grötschel M, ed. Padberg Festschrift The Sharpest Cut (MPS-SIAM, Philadelphia), 233–256.Crossref, Google Scholar
• Johnson E, Mehrotra A, Nemhauser G (1993) Min-cut clustering. Math. Programming 62(1–3):133–152.Crossref, Google Scholar
• Karger D, Motwani R, Sudan M (1998) Approximate graph coloring by semidefinite programming. J. ACM 45(2):246–265.Crossref, Google Scholar
• Karisch SE (1995) Nonlinear approaches for quadratic assignment and graph partition problems. Ph.D. thesis, Technical University Graz, Austria.Google Scholar
• Karisch SE, Rendl F (1998) Semidefnite programming and graph equipartition. Pardalos P, Wolkowicz H, eds. Topics in Semidefinite and Interior–Point Methods (The Fields Institute for Research in Mathematical Sciences, Communications Series, Providence, RI) AMS 18, 77–96.Google Scholar
• Karisch SE, Rendl F, Clausen J (2000) Solving graph bisection problems with semidefinite programming. INFORMS J. Comput. 12(3):177–191.Link, Google Scholar
• Kernighan BW, Lin S (1970) An efficient heuristic procedure for partitioning graphs. Bell System Tech. J. 49(2):291–307.Crossref, Google Scholar
• Lengauer T (1990) Combinatorial Algorithms for Integrated Circuit Layout (Wiley, Chicester, UK).Crossref, Google Scholar
• Lisser A, Rendl F (2003) Graph partitioning using linear and semidefinite programming. Math. Programming, Ser. B 95(1):91–101.Crossref, Google Scholar
• Löfberg J (2004) YALMIP: A toolbox for modeling and optimization in MATLAB. Proc. IEEE CACSD Conference, Taipei, Taiwan, 284–289.Crossref, Google Scholar
• Mobasher A, Sotirov R, Khandani AK (2010) Matrix-lifting SDP for detection in multiple antenna systems. IEEE Trans. Sig. Proc. 58(10):5178–5185.Crossref, Google Scholar
• Povh J, Rendl F (2009) Copositive and semidefinite relaxations of the quadratic assignment problem. Discrete Optim. 6(3):231–241.Crossref, Google Scholar
• Rendl F, Wolkowicz H (1995) A projection technique for partitioning nodes of a graph. Ann. Oper. Res. 58:155–179.Crossref, Google Scholar
• Rinaldi G (1996) Rudy. http://www-user.tu-chemnitz.de/~helmberg/rudy.tar.gz.Google Scholar
• Sanchis L (1989) Multiple-way network partitioning. IEEE Trans. Comput. 38(1):62–81.Crossref, Google Scholar
• Simon HD (1991) Partitioning of unstructured problems for parallel processing. Comput. Syst. Eng. 2(2/3):35–148.Google Scholar
• Sotirov R (2012) SDP relaxations for some combinatorial optimization problems. Anjos MF, Lasserre JB, eds. Handbook of Semidefinite, Conic and Polynomial Optimization: Theory, Algorithms, Software and Applications, Vol. 166 (Springer-Verlag, Heidelberg), 795–820.Crossref, Google Scholar
• Sturm JF (1999) Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Software 11–12:625–653.Crossref, Google Scholar
• Wolkowicz H, Zhao Q (1999) Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96–97:461–479.Crossref, Google Scholar
• Zhao Q, Karisch SE, Rendl F, Wolkowicz H (1998) Semidefinite programming relaxations for the quadratic assignment problem. J. Comb. Optim. 2(1):71–109.Crossref, Google Scholar