University of Leicester
Browse
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.

History

Citation

Theoretical Computer Science, 2019

Author affiliation

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

Version

  • AM (Accepted Manuscript)

Published in

Theoretical Computer Science

Publisher

Elsevier

issn

0304-3975

Acceptance date

2019-05-15

Copyright date

2019

Publisher version

https://www.sciencedirect.com/science/article/pii/S0304397519302853?via=ihub

Notes

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.

Language

en

Usage metrics

    University of Leicester Publications

    Categories

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC