Sum Coloring Interval and κ-Claw Free Graphs with Application to Scheduling Dependent Jobs

摘要

We consider the sum coloring and sum multicoloring problems on several fundamental classes of graphs, including the classes of interval and κ-claw free graphs. We give an algorithm that approximates sum coloring within a factor of 1.796, for any graph in which the maximum κ-colorable subgraph problem is polynomially solvable. In particular, this improves on the previous best known ratio of 2 for interval graphs. We introduce a new measure of coloring, robust throughput, that indicates how "quickly" the graph is colored, and show that our algorithm approximates this measure within a factor of 1.4575. In addition, we study the contiguous (or non-preemptive) sum multicoloring problem on κ-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 κ machines. Assuming that κ is a fixed constant, we obtain the first constant factor approximation for the problem.