Exploiting Low-Rank Structure in Max-K-Cut Problems
arXiv:2602.20376v1 Announce Type: new Abstract: 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 $Oleft(n^{2r-1}right)$ candidate solutions, where $n$ is the dimension of the matrix and $r$ […]