Sum Coloring Interval and k -Claw Free Graphs with Application to SchedulingDependent Jobs

We consider the sum coloring and sum multicoloring problems on severalfundamental classes of graphs, including the classes of interval andk-claw free graphs. We give an algorithm that approximates sum coloring within a factor of 1.796, for any graph in which the maximum k-colorablesubgraph problem is polynomially solvable. In particular, this improves onthe previous best known ratio of 2 for interval graphs. We introduce a newmeasure of coloring, robust throughput}, that indicates how quicklythe graph is colored, and show that our algorithm approximates this measurewithin a factor of 1.4575.In addition, we study the contiguous (or non-preemptive) sum multicoloring problem on k-claw free graphs. This models, for example, the scheduling of dependent jobs on multiple dedicated machines, where each job requires the exclusive use of at most k machines.Assuming that k is a fixed constant, we obtain the first constant factor approximation for the problem.