University of Leicester
TCS-Revised-Final.pdf (424.72 kB)

Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals

Download (424.72 kB)
journal contribution
posted on 2019-05-31, 09:38 authored by T Erlebach, F-H Liu, H-H Liu, M Shalom, P Wong, S Zaks
Motivated by applications in optical networks and job scheduling, we consider the interval coloring problem in a setting where an increasing cost is associated with using a higher color index. The cost of a coloring at any point of the line is the cost of the maximum color index used at that point, and the cost of the overall coloring is the integral of the cost over all points on the line. A coloring of minimum cost is called a minimum skyline coloring. We prove that the problem of computing a minimum skyline coloring is NP-hard and initiate the study of the online setting, where intervals arrive one by one. We give an asymptotically optimal online algorithm for the case of linear color costs and present further results for some variations and generalizations of the problem. Furthermore, we consider the variant of the minimum skyline coloring problem where the intervals are already partitioned into color classes and we only need permute the colors so as to minimize the cost of the coloring. We show that this problem variant is NP-hard and present a 2-approximation algorithm for it.



Theoretical Computer Science, 2019

Author affiliation

/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Informatics


  • AM (Accepted Manuscript)

Published in

Theoretical Computer Science





Acceptance date


Copyright date


Publisher version


The file associated with this record is under embargo until 12 months after publication, in accordance with the publisher's self-archiving policy. The full text may be available through the publisher links provided above.



Usage metrics

    University of Leicester Publications