Solving Graph Bisection Problems with Semidefinite Programming

References

• Alizadeh F. Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization. SIAM J. Optim. (1994) 5:13–51Crossref, Google Scholar
• Ashcraft C.C., Liu J.W.H. Using Domain Decomposition to Find Graph Bisectors. (1995) (York University, North York, Canada) . Technical Report CS-95-08Google Scholar
• Barahona F., Grotschel M., Jünger M., Reinelt G. An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design. Operations Research (1998) 36:493–513Link, Google Scholar
• Boppana R.B. Eigenvalues and Graph Bisection. Proceedings of the 28th IEEE Annual Symposium on Foundations of Computer Science (1987) 280–285Google Scholar
• Brunetta L., Conforti M., Rinaldi G. A Branch-and-Cut Algorithm for the Equicut Problem. Math. Program. (1997) 78:243–263Crossref, Google Scholar
• Bui T.N., Moon B.R. Genetic Algorithm and Graph Partitioning. IEEE Trans. Comput. (1995) 45:841–855Google Scholar
• Clausen J., Larsson Träff J. Implementation of Parallel Branch-and-Bound Algorithms–Experiences with the Graph Partition Problem. Ann. Oper. Res. (1991) 33:331–349Crossref, Google Scholar
• Conforti M., Rao M.R., Sassano S. The Equipartition Polytope I: Formulations, Dimensions and Basic Facets. Math. Program. (1990) 49:49–70Crossref, Google Scholar
• Conforti M., Rao M.R., Sassano S. The Equipartition Polytope II: Valid Inequalities and Facets. Math. Program. (1990) 49:71–90Crossref, Google Scholar
• Diekmann R., Monien B., Preis R., Hsu D.F., Rosenberg A.L., Sotteau D. Using Helpful Sets to Improve Graph Bisections, in Interconnection Networks and Mapping and Scheduling Parallel Computations, DIMACS Series in Discrete Mathematics and Theoretical Computer Science. (1995) 21(AMS, Providence, RI) 57–73Google Scholar
• Donath W.E., Hoffman A.J. Lower Bounds for the Partitioning of Graphs. IBM Journal of Research and Development (1973) 17:420–425Crossref, Google Scholar
• Dongarra J. Performance of Various Computers Using Standard Linear Equations Software. (1997) (Computer Science Department, University of Tennessee, Knoxville, TN) . Technical Report cs-89-85Google Scholar
• Feldmann R., Monien B., Mysliwietz P., Tschöke S. A Better Upper Bound on the Bisection Width of the de Bruijn Networks. STACS '97 Proceedings (1995) 1200:511–522Crossref, Google Scholar
• Ferreira C.E., Martin A., de Souza C.C., Weismantel R., Wolsey L.A. The Node Capacitated Graph Partitioning Problem: A Computational Study. Math. Program. (1998) 81:229–256Crossref, Google Scholar
• Frieze A., Jerrum M. Improved Approximation Algorithms for Max k-Cut and Max Bisection. Proceedings of the 4th International IPCO Conference (1995) 920:1–13Google Scholar
• Goemans M.X., Williamson D.P. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite Programming. J. ACM (1995) 42:1115–1145[A preliminary version entitled “.878-Approximation Algorithms for MAXCUT and MAX2SAT” has appeared in the Proceedings of the 26th Annual ACM Symposium on Theory of Computing, 422–431, 1994.]Crossref, Google Scholar
• Helmberg C. An Interior Point Method for Semidefinite Programming and Max-Cut Bounds. (1994) (Graz University of Technology, Graz, Austria) . Ph.D. ThesisGoogle Scholar
• Helmberg C., Poljak S., Rendl F., Wolkowicz H. Combining Semidefinite and Polyhedral Relaxations to Integer Programs. Proceedings of the 4th International IPCO Conference (1995) 920:124–134Google Scholar
• Helmberg C., Rendl F. Solving Quadratic (0, 1)-Problems by Semidefinite Programs and Cutting Planes. Math. Program. (1998) 82:291–315Crossref, Google Scholar
• Helmberg C., Rendl F., Vanderbei R.J., Wolkowicz H. An Interior Point Method for Semidefinite Programming. SIAM J. Optim. (1996) 6:342–361Crossref, Google Scholar
• Helmberg C., Rendl F., Weismantel R. A Semidefinite Programming Approach to the Quadratic Knapsack Problem. Proceedings of the 5th International IPCO Conference (1996) 1064:175–189Google Scholar
• Helmberg C., Weismantel R., Pardalos P.M., Wolkowicz H. Cutting Plane Algorithms for Semidefinite Relaxations. Topics in Semidefinite and Interior-Point Methods (1998) 18(AMS, Providence, RI) 197–213Fields Institute Communications SeriesCrossref, Google Scholar
• Johnson D.S., Aragon C.R., McGeoch L.A., Schevon C. Optimization by Simulated Annealing: An Experimental Evaluation. Part 1, Graph Partitioning. Operations Research (1989) 37:865–892Link, Google Scholar
• Johnson E.L., Mehrotra A., Nemhauser G.L. Min-Cut Clustering. Math. Program. (1993) 62:133–151Crossref, Google Scholar
• Karisch S.E. Nonlinear Approaches for Quadratic Assignment and Graph Partition Problems. (1995) (Graz University of Technology, Graz, Austria) . Ph.D. ThesisGoogle Scholar
• Karisch S.E., Rendl F., Pardalos P.M., Wolkowicz H. Semidefinite Programming and Graph Equipartition, in Topics in Semidefinite and Interior-Point Methods, Fields Institute Communications Series. (1998) 18(AMS, Providence, RI) 77–95Google Scholar
• Karisch S.E., Rendl F., Clausen J. Solving Graph Bisection Problems with Semidefinite Programming. (1997) (Department of Computer Science, University of Copenhagen, Copenhagen, Denmark) . Technical Report DIKU-TR-97/9Google Scholar
• Kernighan B.W., Lin S. An Efficient Heuristic Procedure for Partitioning Graphs. Bell Syst. Tech. J. (1970) 49:291–307Crossref, Google Scholar
• Kojima M., Shindoh S., Hara S. Interior-Point Methods for the Monotone Linear Complementarity Problem in Symmetric Matrices. SIAM J. Optim. (1997) 7:86–125Crossref, Google Scholar
• Lengauer T.Combinatorial Algorithms for Integrated Circuit Layout (1990) (Wiley, Chichester, NY) Crossref, Google Scholar
• Pirkul H., Rolland E. A Lagrangian Based Heuristic for Uniform Graph Partitioning. (1996) (University of California, Riverside, CA) . working paper, A. Gary Anderson Graduate School of ManagementGoogle Scholar
• Poljak S., Rendl F. Nonpolyhedral Relaxations of Graph-Bisection Problems. SIAM J. Optim. (1995) 5:467–487Crossref, Google Scholar
• Rendl F., Wolkowicz H. A Projection Technique for Partitioning the Nodes of a Graph. Ann. Oper. Res. (1995) 58:155–180Crossref, Google Scholar
• Rolland E., Pirkul H., Glover F. Tabu Search for Graph Partitioning. Ann. Oper. Res. (1996) 63:209–232Crossref, Google Scholar
• de Souza C.C., Keunings R., Wolsey L.A., Zone O. A New Approach to Minimising the Frontwidth in Finite Element Calculations. Computer Methods in Applied Mechanics and Engineering (1994) 111:323–334Crossref, Google Scholar
• Wolkowicz H., Zhao Q. Semidefinite Programming Relaxations for the Graph Partition Problem. (1996) (Department of Combinatorics and Optimization, University of Waterloo, Waterloo, Canada) . Research Report CORRGoogle Scholar