On the Hardness of Approximating Max k-Cut and Its Dual
Viggo Kann, Sanjeev Khanna, Jens Lagergren, Alessandro Panconesi · 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 6= 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 ffl ? 0, there exists a constant ff such that the problem cannot be approximated within ffjV j 2\\Gammaffl , even for dense graphs. Both problems are directly related to the frequency allocation problem for cellular (mobile) telephones, an application of industrial relevance. 1 Introduction In order to motivate the problems studied in this paper, consider the frequency allocation problem for cellular telephones. We are given a fixed set of k freque...