APPROXIMATION TECHNIQUES FOR HYPERGRAPH PARTITIONING PROBLEMS

Techniques for approximating a hypergraph by a weighted graph for use in node partitioning algorithms are described. The graphs use the same node set as the hypergraph and their edges are obtained by generating a series of cliques that correspond to subsets of the hyper edges. Ed ge weights are obtained by characterizing optimal solutions to mathema tical programs that describe properties of feasible partitions of the hypergraph, These approximations are compared with other known approxi mations and yield promising results.