Approximate max k-cut with subgraph guarantee
Kann, Viggo ;  Lagergren, Jens ;  Panconesi, Alessandro ;  Universität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik

Main titleApproximate max k-cut with subgraph guarantee
AuthorKann, Viggo
AuthorLagergren, Jens
AuthorPanconesi, Alessandro
InstitutionUniversität <Berlin, Freie Universität> / Fachbereich Mathematik und Informatik
No. of Pages[8] S.
Series Freie Universität Berlin, Fachbereich Mathematik [und Informatik] : Ser. B, Informatik ; 96,08
Classification (DDC)004 Data processing and Computer science
AbstractWe 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\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.
If your browser can't open the file, please download the file first and then open it
FU DepartmentDepartment of Mathematics and Computer Science
Other affiliation(s)Institut für Informatik
Year of publication1996
Type of documentWorking paper
Terms of use/Rights Nutzungsbedingungen
Created at2009-03-19 : 02:46:04
Last changed2015-03-25 : 12:49:43
Static URLhttp://edocs.fu-berlin.de/docs/receive/FUDOCS_document_000000001326