@inproceedings{5a8e16c1514c4bd5943a29cd7ac8cc16,
title = "Recursive randomized coloring beats fair dice random colorings",
abstract = "We investigate a refined recursive coloring approach to construct balanced colorings for hypergraphs. A coloring is called balanced if each hyperedge has (roughly) the same number of vertices in each color. We provide a recursive randomized algorithm that colors an arbitrary hypergraph (n vertices, m edges) with c colors with discrepancy at most O(formula presented). The algorithm has expected running time O(nmlog c). This result improves the bound of O(formula presented) achieved with probability at least 1\textbackslash{}2 by a random coloring that independently chooses a random color for each vertex (fair dice coloring). Our approach also lowers the current best upper bound for the c-color discrepancy in the case (formula presented) and extends the algorithm of Matou{\v s}ek, Welzl and Wernisch for hypergraphs having bounded dual shatter function to arbitrary numbers of colors.",
author = "Benjamin Doerr and Anand Srivastav",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001.; 18th Annual Symposium on Theoretical Aspects of Computer Science, STACS 2001 ; Conference date: 15-02-2001 Through 17-02-2001",
year = "2001",
month = jan,
day = "1",
doi = "10.1007/3-540-44693-1\_16",
language = "English",
isbn = "9783540416951",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "183--194",
editor = "Afonso Ferreira and Horst Reichel",
booktitle = "STACS 2001 - 18th Annual Symposium on Theoretical Aspects of Computer Science, Proceedings",
}