## Approximate Max *k*-Cut with Subgraph Guarantee

###
Viggo Kann (viggo@nada.kth.se)

Jens Lagergren (jensl@nada.kth.se)

Alessandro Panconesi

Institut für Informatik

Freie Universität Berlin

email: ale@inf.fu-berlin.de

Report B-96-08

August 1996

We study the following variant of the Max *k*-Cut problem.
Given an input graph *G* with positively weighted edges and *k* colors - the number *k* being fixed and not dependent on the input instance -
we wish to compute a subgraph *H* of *G* containing "lots"
of heavy edges and a color assignment *c:V ->[k]* such that:
(a) all edges in *H* are properly colored and (b) a "large fraction"
of edges in $G\setminus H$ is properly colored.
We give several definitions of ``lots'' and ``large fraction'' and
give fast polynomial time algorithms to compute such color assignments.
This problem is related to the frequency allocation problems
for cellular telephone networks but could be useful in other scenarios
too.

Get the report here or by anonymous ftp:
Server: ftp.inf.fu-berlin.de
File: pub/reports/tr-b-96-08.ps.gz