Multicoloring trees |
| |
| Authors: | Magnús M Halldrsson Guy Kortsarz Andrzej Proskurowski Ravit Salman Hadas Shachnai Jan Arne Telle |
| |
| Affiliation: | a Department of Computer Science, University of Iceland, IS-107, Reykjavik, Iceland;b Department of Computer Science, Rutgers University, Camden, NJ, USA;c Department of Computer Science, University of Oregon, Eugene, OR, USA;d Department of Mathematics, Technion, Haifa 32000, Israel;e Department of Computer Science, Technion, Haifa 32000, Israel;f Department of Informatics, University of Bergen, Bergen, Norway |
| |
| Abstract: | 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. |
| |
| Keywords: | Multicoloring Approximation algorithms Resource allocation Scheduling |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
