Graph Partitioning with Demands: Generalized Conductance and its Applications
The work studies graph partitioning problems under a general demand model using a new objective called Generalized Conductance. It develops an approximation algorithm for this problem, which is then used to solve Graph Partitioning with Demands and Hierarchical Clustering with Demands. The results provide O(log n) approximation guarantees on general graphs and O(1) on trees.