# Graph Partitioning with Demands: Generalized Conductance and its Applications

arXiv: https://arxiv.org/abs/2607.13218 · HTML: https://mlsanity.com/paper/2607.13218/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 26 references that are in the map.
- First posted on arXiv 14 Jul 2026.

## Builds on (most cited first, 3 of 3)

- [A cost function for similarity-based hierarchical clustering](https://mlsanity.com/paper/1510.05043/) (2015)
- [Approximate Hierarchical Clustering via Sparsest Cut and Spreading Metrics](https://mlsanity.com/paper/1609.09548/) (2016)
- [The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative Type Metrics into ℓ1](https://mlsanity.com/paper/1305.4581/) (2013)

## Abstract (arXiv)

In this work, we study various graph partitioning problems under a general demand model. In each such task, we are given a graph G=(V,E,c,w) with a capacity function ccolon E→ mathbbN and a demand function wcolon V× V→ mathbbN. Our main focus is the problem of finding a cut (S, barS) minimizing the quantity [ psiw( S ) = fracc( S, barS )w( S, V )· w( barS, V ). ] Here, c( S, barS ) is the cost of edges between S and the complement of S, barS, and w( S, V )=w( S )+w( S, barS ) is the sum of the internal demand within S, w( S ), and the demand between vertices of S and barS, w( S, barS ). We call psiw( S ) the generalized conductance of the cut (S, barS), and the task of minimizing psiw( S ) the Generalized Conductance Problem. Our main contribution is an algorithm with an O(log n)-approximation guarantee for this objective. Our result is achieved via a two-way reduction: first to the well-known Generalized k-Multicut Problem, and then to a constrained variant of the classic Sparsest-Cut Problem, with an additional upper-bound constraint on the amount of demand that may be cut. Moreover, we show that the above procedure can be used to obtain an O(log n)-bicriteria approximation for Graph Partitioning with Demands, where the goal is to find a minimum-cost subset of edges C such that for every component H of Gsetminus C, w( H )≤ ρ· w( V ). This, in turn, yields an O(log n)-approximation for Hierarchical Clustering with Demands, the problem of finding a hierarchy of cuts that partitions the graph into increasingly refined clusters. For multiplicative demand functions, we improve these guarantees to O(√log n) and for trees we get an O(1)-approximation for all of our objectives.