Balanced Interval Coloring

Antonios Antoniadis, Falk Hüffner, Pascal Lenzner, Carsten Moldenhauer, Alexander Souza

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

2 Downloads (Pure)

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 non-constructive. 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 NP-complete to decide if such a solution exists, which implies also NP-hardness 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.
Original languageEnglish
Title of host publication28th International Symposium on Theoretical Aspects of Computer Science
Subtitle of host publicationSTACS’11, March 10–12, 2011, Dortmund, Germany
EditorsThomas Schwentick, Christoph Dürr
Place of PublicationSaarbrücken/Wadern
PublisherDagstuhl
Pages531-542
Number of pages12
ISBN (Print)978-3-939897-25-5
DOIs
Publication statusPublished - 2011
Externally publishedYes
Event28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011 - Dortmund, Germany
Duration: 10 Mar 201112 Mar 2011
Conference number: 28

Publication series

NameLIPIcs–Leibniz International Proceedings in Informatics
PublisherSchloss Dagstuhl
ISSN (Print)1868-8969

Conference

Conference28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011
Abbreviated titleSTACS 2011
Country/TerritoryGermany
CityDortmund
Period10/03/1112/03/11

Fingerprint

Dive into the research topics of 'Balanced Interval Coloring'. Together they form a unique fingerprint.

Cite this