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.

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/34*k*. 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

Article 1 Article 3

Volume 1997 Published articles

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