1 Graph Partitioning Metrics
We want to find a low cost cut that doesn't
result in pieces that are ``too small''.
There are multiple ways to express the
desire for balance. For example:
- Hard Balance Constraint (Metis)
-
perfect 50-50 balance required
- floor (say 30 %) on small side size
- Tradeoff-style metric (isoperimeter problem).
-
cutsize / min(a,b) ... [expansion]
- cutsize / a * b ... [approx. expansion]
- cutsize / min(Da,Db) ... [conductance]
- cutsize / Da * Db ... [approx. conductance, aka normalized cut]
