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.

Abstract

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.

• Preformatted versions of the article
  • DVI (67,380 bytes)
  • PostScript (266,663 bytes)
  • PDF (327,860 bytes)
  • Audio by AsTeR (to appear)
• Source materials for custom formatting
  • LaTeX (cj97-02.tex, 49,940 bytes)
  • BIBTeX (cj97-02.bib, 5,523 bytes)
  • Parameter settings for custom formatting (cjropts.tex, 165 bytes)
  • Self citation in BIBTeX (386 bytes)
• Online discussion
• Instructions for Readers

DOI: 10.4086/cjtcs.1997.002

---

Article 1 Article 3
Volume 1997 Published articles

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