Application of Semidefinite Programming to Circuit
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
Department of Management Sciences
The University of Iowa
Iowa City, Iowa 52242, U.S.A.