Application of Semidefinite Programming to Circuit Partitioning

Changhui Cris Choi and Yinyu Ye

In this paper we apply Semidefinite Programming (SDP) to solving the circuit partition problem. Unlike other local search methods, we first translate the hypergraph into a weighted (undirected) graph, and then solve it as a graph partition problem using the recent semidefinite program relaxation and heuristic or randomized approximation. Our preliminary computational results indicate that as the number of modules in the circuit increases, the quality of the partition resulted from SDP becomes superior to that resulted from previous methods.

Department of Management Sciences The University of Iowa Iowa City, Iowa 52242, U.S.A.