Clique Clustering Yields a PTAS for Max-Coloring Interval Graphs

Abstract

We are given an interval graph G= (V, E) where each interval I∈ V has a weight wI∈ Q+. The goal is to color the intervals V with an arbitrary number of color classes C1, C2, … , Ck such that ∑i=1kmaxI∈CiwI is minimized. This problem, called max-coloring interval graphs or weighted coloring interval graphs, contains the classical problem of coloring interval graphs as a special case for uniform weights, and it arises in many practical scenarios such as memory management. Pemmaraju, Raman, and Varadarajan showed that max-coloring interval graphs is NP-hard [21] and presented a 2-approximation algorithm. We settle the approximation complexity of this problem by giving a polynomial-time approximation scheme (PTAS), that is, we show that there is an (1 + ϵ) -approximation algorithm for any ϵ> 0. The PTAS also works for the bounded case where the sizes of the color classes are bounded by some arbitrary k≤ n.