Complexity and Online Algorithms for Minimum Skyline Coloring of Intervals

2^nd November 2017, 14:00
Prof Prudence Wong

Abstract

Graph coloring has been studied extensively in the literature. The classical problem concerns the number of colors used. In this talk we focus on coloring intervals
where the input is a set of intervals and two overlapping intervals cannot be assigned the same color. In particular, we are interested in the setting where there is an increasing cost associated with using a higher color index. Given a set of intervals (on a line) and a coloring, the cost of the coloring at any point 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. The objective is to assign a valid color to each interval and minimize the total cost of the coloring. Intuitively, the maximum color index used at each point forms a skyline and so the objective is to obtain a minimum skyline coloring. The problem arises in various applications including optical networks and job scheduling.

This is a joint work with: Thomas Erlebach, Fu-Hong Liu, Hsiang-Hsuan Liu, Mordechai Shalom, and Shmuel Zaks.