Multicoloring trees

Scheduling jobs with pairwise conflicts is modeled by the graph multicoloring problem. It occurs in two versions: in the preemptive case, each vertex may get any set of colors, while in the non-preemptive case, the set of colors assigned to each vertex has to be contiguous. We study these versions of the multicoloring problem on trees, under the sum-of-completion-times objective. In particular, we give a quadratic algorithm for the non-preemptive case, and a faster algorithm in the case that all job lengths are short, while we present a polynomial-time approximation scheme for the preemptive case.

Authors

• Magnús M. Halldórsson
• Guy Kortsarz
• Andrzej Proskurowski
• Ravit Salman
• Hadas Shachnai
• Jan Arne Telle

Keywords

• Multicoloring
• Approximation algorithms
• Resource allocation
• Scheduling