@inproceedings{110704d5ddd24338b90d78cb8ec1f981,
title = "Balanced coloring: Equally easy for all numbers of colors?",
abstract = "We investigate the problem to color the vertex set of a hypergraph H = (X,ε) with a fixed number of colors in a balanced manner, i.e., in such a way that all hyperedges contain roughly the same number of vertices in each color (discrepancy problem). We show the following result: Suppose that we are able to compute for each induced subhypergraph a coloring in c1 colors having discrepancy at most D. Then there are colorings in arbitrary numbers c2 of colors having discrepancy at most 11/10 c21D. A c2-coloring having discrepancy at most 11/10 c21D +3c1-k|X|can be computed from (c1 -1)(c2 -1) k colorings in c1 colors having discrepancy at most D with respect to a suitable subhypergraph of H. A central step in the proof is to show that a fairly general rounding problem (linear discrepancy problem in c2 colors) can be solved by computing low-discrepancy c1–colorings.",
author = "Benjamin Doerr",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2002.; 19th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2002 ; Conference date: 14-03-2002 Through 16-03-2002",
year = "2002",
month = jan,
day = "1",
doi = "10.1007/3-540-45841-7\_8",
language = "English",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "112--120",
editor = "Helmut Alt and Afonso Ferreira",
booktitle = "STACS 2002 - 19th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
}