Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Balanced Coloring: Equally Easy for All Numbers of Colors?

Benjamin DoerrContact Information

(6)  Mathematisches Seminar II, Christian-Albrechts-Universität zu Kiel, Ludewig-Meyn-Str.4, D-24098 Kiel, Germany
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 c 1 2 D. A c2-coloring having discrepancy at most 11/10 c 1 2 D+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.

Contact Information Benjamin Doerr
Email: bed@numerik.uni-kiel.de
URL: http://www.numerik.uni-kiel.de/~bed/
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.106 • Server: mpweb23
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)