Journal article
A semidefinite programming approach to the hypergraph minimum bisection problem
Optimization, Vol.60(3), pp.413-427
03/01/2011
DOI: 10.1080/02331930903233744
Abstract
The hypergraph minimum bisection (HMB) problem is the problem of partitioning the vertices of a hypergraph into two sets of equal size so that the total weight of hyperedges crossing the sets is minimized. HMB is an NP-hard problem that arises in numerous applications - for example, in digital circuit design. Although many heuristics have been proposed for HMB, there has been no known mathematical program that is equivalent to HMB. As a means of shedding light on HMB, we study the equivalent, complement problem of HMB (called CHMB), which attempts to maximize the total weight of non-crossing hyperedges. We formulate CHMB as a quadratically constrained quadratic program, considering its semidefinite programming relaxation and providing computational results on digital circuit partitioning benchmark problems. We also provide results towards an approximation guarantee for CHMB.
Details
- Title: Subtitle
- A semidefinite programming approach to the hypergraph minimum bisection problem
- Creators
- Changhui Choi - Univ Colorado, Dept Math & Stat Sci, Denver, CO 80217 USASamuel Burer - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Optimization, Vol.60(3), pp.413-427
- Publisher
- Taylor & Francis
- DOI
- 10.1080/02331930903233744
- ISSN
- 0233-1934
- eISSN
- 1029-4945
- Number of pages
- 15
- Grant note
- CCR-0203426; CCF-0545514 / NSF; National Science Foundation (NSF)
- Language
- English
- Date published
- 03/01/2011
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380398202771
Metrics
3 Record Views