Balanced Interval Coloring

Antonios Antoniadis, Falk Hueffner, Pascal Lenzner, Carsten Moldenhauer & Alexander Souza
We consider the discrepancy problem of coloring n intervals with k colors such that at each point on the line, the maximal difference between the number of intervals of any two colors is minimal. Somewhat surprisingly, a coloring with maximal difference at most one always exists. Furthermore, we give an algorithm with running time O(n log n + kn log k) for its construction. This is in particular interesting because many known results for discrepancy...