Max-Coloring and Online Coloring with Bandwidths on Interval Graphs

Given a graph G = (V, E) and positive integral vertex weights w : V -> N, the max-coloring problem seeks to find a proper vertex coloring of G whose color classes C-1, C-2,C- ... , C-k, minimize Sigma(k)(i=1) max(v epsilon Ci) w(v). This problem, restricted to interval graphs, arises whenever there is a need to design dedicated memory managers that provide better performance than the general-purpose memory management of the operating system. Though this problem seems similar to the dynamic storage allocation problem, there are fundamental differences. We make a connection between max-coloring and online graph coloring and use this to devise a simple 2-approximation algorithm for max-coloring on interval graphs. We also show that a simple first-fit strategy, that is a natural choice for this problem, yields an 8-approximation algorithm. We show this result by proving that the first-fit algorithm for online coloring an interval graph G uses no more than 8 . chi(G) colors, significantly improving the bound of 26 . chi(G) by Kierstead and Qin [1995]. We also show that the max-coloring problem is NP-hard. The problem of online coloring of intervals with bandwidths is a simultaneous generalization of online interval coloring and online bin packing. The input is a set I of intervals, each interval i epsilon I having an associated bandwidth b(i) epsilon (0, 1]. We seek an online algorithm that produces a coloring of the intervals such that for any color c and any real r, the sum of the bandwidths of intervals containing r and colored c is at most 1. Motivated by resource allocation problems, Adamy and Erlebach [2003] consider this problem and present an algorithm that uses at most 195 times the number of colors used by an optimal offline algorithm. Using the new analysis of first-fit coloring of interval graphs, we show that the Adamy-Erlebach algorithm is 35-competitive. Finally, we generalize the Adamy-Erlebach algorithm to a class of algorithms and show that a different instance from this class is 30-competitive.