Some Objective Functions

This section talks about various objective functions that were defined in the literature. Some of the notations used are as follows:

The set of the hyperedges cut by a cluster C is given by

i.e. if at least one, but not all the vertices of e are in C. The set of hyperedges cut by a clustering solution is given by

1. Scaled Cost

   To integrate the cut size and the cluster size balance within a signle pbjective, Chan et.al[20] have propsed the Scaled Cost objective which is as follows.
   Minimize

   This is a k-way generalization of the ratio cut objective in standard graph bipartitioning problems.

2. Absorption

   The absorption objective as described in [3] measures the sum of the fraction of hyperedges ``absorbed'' by the clusters. If this fraction is maximized, clealry the edge cut of the resulting clustering will be minimized. The objective is stated as follows:
   Maximize

   

   e.g., hyperedge e incident to cluster adds absorption zero if it has only one vertex in , and adds absorption one if all of its vertices are in . Absorption objective was proposed specifically for standard cell placement.

3. Density

   This objective as described in [3] maximizes the sum of cluster densities, where the density of a cluster C is the number of the hyperedges completely contained in C, divided by th weight of C. Thus the objective is :
   Maximize

   Density differs from absorption in that only the hyperedges completey absorbed in the cluster are counted.