Antoniadis, Antonios ;
Hueffner, Falk ;
Lenzner, Pascal ;
Moldenhauer, Carsten ;
Souza, Alexander
Balanced Interval Coloring
Abstract
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 problems are nonconstructive. This problem naturally models a load balancing scenario, where $n$~tasks with given start and endtimes have to be distributed among $k$~servers. Our results imply that this can be done ideally balanced.
When generalizing to $d$dimensional boxes (instead of intervals), a solution with difference at most one is not always possible. We show that for any d >= 2 and any k >= 2 it is NPcomplete to decide if such a solution exists, which implies also NPhardness of the respective minimization problem.
In an online scenario, where intervals arrive over time and the color has to be decided upon arrival, the maximal difference in the size of color classes can become arbitrarily high for any online algorithm.
BibTeX  Entry
@InProceedings{antoniadis_et_al:LIPIcs:2011:3041,
author = {Antonios Antoniadis and Falk Hueffner and Pascal Lenzner and Carsten Moldenhauer and Alexander Souza},
title = {{Balanced Interval Coloring}},
booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
pages = {531542},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897255},
ISSN = {18688969},
year = {2011},
volume = {9},
editor = {Thomas Schwentick and Christoph D{\"u}rr},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2011/3041},
URN = {urn:nbn:de:0030drops30413},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2011.531},
annote = {Keywords: Load balancing, discrepancy theory, NPhardness}
}
2011
Keywords: 

Load balancing, discrepancy theory, NPhardness 
Seminar: 

28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Issue date: 

2011 
Date of publication: 

2011 