@inproceedings{361d6ab4f4a6485495b770b596b41314,
title = "Approximation of multi-color discrepancy",
abstract = "In this article we introduce (combinatorial) multi-color discrepancy and generalize some classical results from 2-color discrepancy theory to c colors. We give a recursive method that constructs c-colorings from approximations to the 2-color discrepancy. This method works for a large class of theorems like the six-standard-deviation theorem of Spencer, the Beck-Fiala theorem and the results of Matou{\v s}ek, Welzl and Wernisch for bounded VC-dimension. On the other hand there are examples showing that discrepancy in c colors can not be bounded in terms of two-color discrepancy even if c is a power of 2. For the linear discrepancy version of the Beck-Fiala theorem the recursive approach also fails. Here we extend the method of oating colors to multi-colorings and prove multi-color versions of the the Beck-Fiala theorem and the Barany-Grunberg theorem.",
author = "Benjamin Doerr and Anand Srivastav",
note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 1999.; 3rd International Workshop on Randomization and Approximation Techniques in Computer Science and 2nd International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, RANDOM-APPROX 1999 ; Conference date: 08-08-1999 Through 11-08-1999",
year = "1999",
month = jan,
day = "1",
doi = "10.1007/978-3-540-48413-4\_5",
language = "English",
isbn = "3540663290",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "39--50",
editor = "Rolim, \{Jose D. P.\} and Alistair Sinclair and Dorit Hochbaum and Klaus Jansen",
booktitle = "Randomization, Approximation, and Combinatorial Optimization",
}