Sum Coloring Interval and k -Claw Free Graphs with Application to SchedulingDependent Jobs |
| |
Authors: | Magnús M. Halldórsson Guy Kortsarz Hadas Shachnai |
| |
Affiliation: | (1) Department of Computer Science, University of Iceland, IS-107 Reykjavik, Iceland;(2) Department of Computer Science, Rutgers University, Camden, NJ 08102, USA;(3) Department of Computer Science, The Technion, Haifa 32000, Israel |
| |
Abstract: | 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 quickly the 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. |
| |
Keywords: | Sum Coloring Multicoloring Scheduling dependent jobs Approximation algorithms |
本文献已被 SpringerLink 等数据库收录! |
|