Max-$k$-Cut via Node Features
TL;DR
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 optimality-gap certificate that depends only on the returned partition and requires no knowledge of the optimum.
Abstract
We study the Max-$k$-Cut problem from a node-feature perspective, where each vertex is associated with a feature vector and edge weights are given by pairwise inner products. We first examine the semidefinite relaxation of Max-$k$-Cut from this perspective. Using a normal-cone argument, we derive a general sufficient condition for exactness of the Frieze--Jerrum relaxation and show that it is satisfied in two feature-structural regimes: perfect feature balance, where the aggregate feature vectors of the parts are equal, and feature dominance, where a small set of large nonnegative feature vectors determines the structure of an optimal partition. We then show that the Max-$k$-Cut objective is equivalent to minimizing the sum of squared norms of the aggregate feature vectors assigned to the $k$ parts, thereby connecting the problem to vector balancing. Motivated by this observation, we show that a greedy feature-balancing algorithm retains the classical $1-1/k$ worst-case approximation guarantee and recovers an optimal partition under feature dominance. For rank-$1$ feature graphs with nonnegative features, classical bounds of Chandra and Wong for greedy load balancing yield a computable \emph{a posteriori} optimality-gap certificate that depends only on the returned partition and requires no knowledge of the optimum.