A semidefinite programming approach to the hypergraph minimum bisection problem

References

• Alpert , CJ . The ISPD98 circuit benchmark suite, Proceedings of the 1998 International Symposium on Physical Design, 1998, pp. 80–85
   Google Scholar
• Alpert , CJ and Kahng , AB . Recent directions in netlist partitioning: A survey, PhD thesis, Computer Science Department, UCLA, Los Angeles, 1995
   Google Scholar
• Arora , S , Rao , S and Vazirani , U . Expander flows, geometric embeddings and graph partitioning, Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004, pp. 222–231
   Google Scholar
• Berman , P and Karpinski , M . Approximability of hypergraph minimum bisection, Technical Report, 2003. Available at http://www.maths.ox.ac.uk/rand-apx/, rAND-APX Thematic Network
   Google Scholar
• Burer , S and Choi , C . 2006 . Computational enhancements in low-rank semidefinite programming . Optim. Methods Software , 21 : 493 – 512 .
   Web of Science ®Google Scholar
• Burer , S and Monteiro , R . 2003 . A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization . Math. Program. (Series B) , 95 : 329 – 357 .
   Web of Science ®Google Scholar
• Choi , C and Ye , Y . 2000 . “ Application of semidefinite programming to circuit partitioning ” . In Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems , Edited by: Pardalos , P . 130 – 136 . Dordrecht : Kluwer Academic Press .
   Google Scholar
• Feige , U and Krauthgamer , R . 2002 . A polylogarithmic approximation of the minimum bisection . SIAM J. Comput. , 31 : 1090 – 1118 .
   Google Scholar
• Fiduccia , CM and Mattheyses , RM . A linear time heuristic for improving network partitions, Proceedings of the 19th IEEE Design Automation Conference, 1982, pp. 175–181
   Google Scholar
• Frieze , A and Jerrum , M . 1997 . Improved approximation algorithms for max k-cut and max bisection . Algorithmica , 18 : 61 – 77 .
   Google Scholar
• Garey , MR , Johnson , DS and Stockmeyer , L . 1976 . Some simplified NP-complete graph problems . Theor. Comput. Sci. , 1 : 237 – 267 .
   Google Scholar
• Goemans , M and Williamson , D . 878-Approximation algorithms for MAX CUT and MAX 2SAT, Proceedings of the Symposium of Theoretical Computer Science, 1994, pp. 422–431
   Google Scholar
• Goemans , M and Williamson , D . 1995 . Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming . J. ACM , 42 : 1115 – 1145 .
   Web of Science ®Google Scholar
• Ihler , E , Wagner , D and Wagner , F . 1993 . Modeling hypergraphs by graphs with the same mincut properties . Inform. Process. Lett. , 45 : 171 – 175 .
   Google Scholar
• Karypis , G , Aggarwal , R , Kumar , V and Shekhar , S . 1999 . Multilevel hypergraph partitioning: Applications in VLSI domain . IEEE Trans. VLSI Syst. , 7 : 69 – 79 .
   Web of Science ®Google Scholar
• Karypis , G and Kumar , V . 1998 . “ Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices, version 4.0 ” . In Technical Report , Minneapolis, MN 55455, , USA : Department of Computer Science, University of Minnesota .
   Google Scholar
• Karypis , G and Kumar , V . Multilevel k-way hypergraph partitioning, Proceedings of the 36th ACM Design Automation Conference, 1999, pp. 343–348
   Google Scholar
• Saab , YG . 1995 . A fast network bisection algorithm . IEEE Trans. Comput. , 44 : 903 – 913 .
   Google Scholar
• Ye , Y . 2001 . A. 699-Approximation algorithm for max-bisection . Math. Program. , 90 : 101 – 111 .
   Google Scholar
• Ye , Y and Zhang , J . 2003 . Approximation of dense-n/2-subgraph and the complement of minbisection . J. Global Optim. , 25 : 55 – 73 .
   Web of Science ®Google Scholar