Exploiting Low-Rank Structure in Max-K-Cut Problems
This addresses graph partitioning problems for researchers and practitioners, offering a scalable alternative to classical methods, though it is incremental as it builds on low-rank approximations.
The paper tackled the Max-3-Cut problem by exploiting low-rank structure in the objective matrix, proposing an algorithm that enumerates O(n^{2r-1}) candidate solutions and achieves performance comparable to existing algorithms while being highly scalable.
We approach the Max-3-Cut problem through the lens of maximizing complex-valued quadratic forms and demonstrate that low-rank structure in the objective matrix can be exploited, leading to alternative algorithms to classical semidefinite programming (SDP) relaxations and heuristic techniques. We propose an algorithm for maximizing these quadratic forms over a domain of size $K$ that enumerates and evaluates a set of $O\left(n^{2r-1}\right)$ candidate solutions, where $n$ is the dimension of the matrix and $r$ represents the rank of an approximation of the objective. We prove that this candidate set is guaranteed to include the exact maximizer when $K=3$ (corresponding to Max-3-Cut) and the objective is low-rank, and provide approximation guarantees when the objective is a perturbation of a low-rank matrix. This construction results in a family of novel, inherently parallelizable and theoretically-motivated algorithms for Max-3-Cut. Extensive experimental results demonstrate that our approach achieves performance comparable to existing algorithms across a wide range of graphs, while being highly scalable.