Chicago Journal of Theoretical Computer Science

Volume 1997

Article 2

Published by MIT Press. Copyright 1997 Massachusetts Institute of Technology.

Your institution may already be a subscriber to CJTCS. If not, please subscribe for legitimate access to all journal articles.

On the Hardness of Approximating Max k-Cut and Its Dual

Viggo Kann (Royal Institute of Technology, Sweden), Sanjeev Khanna (Bell Laboratories), Jens Lagergren (Royal Institute of Technology, Sweden), Alessandro Panconesi (The Swedish Institute of Computer Science)
3 June 1997

We study the Max k-Cut problem and its dual, the Min k-Partition problem. In the Min k-Partition problem, given a graph G=(V,E) and positive 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, if P&neq;NP, no polynomial time approximation algorithm can achieve a relative error better than 1/34k. It is well known that a relative 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 approximated 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.

DOI: 10.4086/cjtcs.1997.002
[] Article 1 [] Article 3
[back] Volume 1997 [back] Published articles
[CJCTS home]

Last modified: Tue Nov 4 20:03:58 CST