Timezone: »

The Product Cut
Thomas Laurent · James von Brecht · Xavier Bresson · arthur szlam

Tue Dec 06 09:00 AM -- 12:30 PM (PST) @ Area 5+6+7+8 #72

We introduce a theoretical and algorithmic framework for multi-way graph partitioning that relies on a multiplicative cut-based objective. We refer to this objective as the Product Cut. We provide a detailed investigation of the mathematical properties of this objective and an effective algorithm for its optimization. The proposed model has strong mathematical underpinnings, and the corresponding algorithm achieves state-of-the-art performance on benchmark data sets.

Author Information

Thomas Laurent (Loyola Marymount University)
James von Brecht (CSULB)
Xavier Bresson (EPFL)
arthur szlam (Facebook)

More from the Same Authors