Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small kResearch Paper
In Max--Cut one is given a graph with non-negative edge weights and must colour its vertices with colours so as to maximise the total weight of the edges whose endpoints receive different colours. For this is Max-Cut. For the best polynomial-time algorithms round the semidefinite relaxation of Frieze and Jerrum (Algorithmica 1997); for …