Clique Clustering Yields a PTAS for max-Coloring Interval Graphs

We are given an interval graph

G

 = (

V

,

E

) where each interval

I

 ∈ 

V

has a weight

w

I

 ∈ ℝ

 + 

. The goal is to color the intervals

V

with an arbitrary number of color classes

C

1

,

C

2

, …,

C

k

such that

$ \sum_{i=1}^k \max_{I \in C_i} w_I $

is minimized. This problem, called max-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 (SODA’04) and presented a 2-approximation algorithm. Closing a gap which has been open for years, 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 . Besides using standard preprocessing techniques such as geometric rounding and shifting, our main building block is a general technique for trading the overlap structure of an interval graph for accuracy, which we call clique clustering.