Preprint
Aug 2026
Max-$k$-Cut via Node Features
It is shown that a greedy feature-balancing algorithm retains the classical $1-1/k$ worst-case approximation guarantee and recovers an optimal partition under feature dominance and for rank-$1$ feature graphs with nonnegative features, classical bounds of Chandra and Wong for greedy load balancing yield a computable op...
Avinash Bhardwaj, Hritiz Gogoi, Vishnu Narayanan
· 1 citation