ROS: A GNN-based Relax-Optimize-and-Sample Framework for Max-k-Cut Problems

Yeqing Qiu, Ye Xue, Akang Wang +3

The Max-k-Cut problem is a fundamental combinatorial optimization challenge that generalizes the classic NP-complete Max-Cut problem. While relaxation techniques are commonly emplo…