In the Sum Coloring problem, we are given a graph of n vertices and the set of colors 1,2,... The cost of coloring a vertex with i is equal to i. We need to assign colors to the vertices, so that adjacent vertices receive distinct colors, and the total cost is minimized. In the generalized version, known as the Sum Multicoloring problem, each vertex requires a (contiguous) set of colors, and the objective is to find a multicoloring which minimizes the sum of the largest colors assigned to the vertices. Sum Coloring and its generalizations have natural applications in scheduling, distributed resource allocation, compiler design and VLSI routing.
While in general Sum Coloring is no easier than the classic graph coloring problem, we have shown that it can be approximated to within constant factor on several subclasses of graphs, through a relation to the maximum independent set and the maximum k-colorable subgraph problems. However, the best known approximation ratio for Sum Multicoloring was O(log n), for many classes of graphs, including interval graphs that often arise in applications.
In a recent paper, we give a general paradigm for reducing the Sum Multicoloring problem to classical graph multicoloring, where the objective is minimizing the number of colors. Using this paradigm, we improve the best known results for Sum Multicoloring on several fundamental classes of graphs. In particular, we obtain the first constant factor approximation ratio for Sum Multicoloring of interval graphs.
This talk is based on joint papers with Amotz Bar-Noy, Mihir Bellare, Magnus Halldorsson, Guy Kortsarz, Ravit Salman and Tami Tamir.