ON THE HARDNESS OF APPROXIMATING MAX K-CUT AND ITS DUAL

We study the MAX k-CUT problem and its dual, the MIN k-PARTITION probl em. In the MIN k-PARTITION problem, given a graph G = (V, E) and posit ive edge weights, we want to find an edge set of minimum weight whose removal makes G k-colorable. For the MAX k-CUT problem we show that, i f P not equal NP, no polynomial time approximation algorithm can achie ve a relative error better than 1/(34k). It is well known that a relat ive error of 1/k is obtained by a naive randomized heuristic. For the MIN k-PARTITION problem, we show that for k>2 and for every epsilon>0, there exists a constant alpha such that the problem cannot be approxi mated within alpha\V\(2-epsilon), even for dense graphs. Both problems are directly related to the frequency allocation problem for cellular (mobile) telephones, an application of industrial relevance.