תקציר
Scheduling jobs with pairwise conflicts is modeled by the graph multi-coloring problem. It occurs in two versions: preemptive and non-preemptive. We study these problems 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.
שפה מקורית | אנגלית |
---|---|
כותר פרסום המארח | Computing and Combinatorics - 5th Annual International Conference, COCOON 1999, Proceedings |
עורכים | Shin-ichi Nakano, Hideki Imai, D.T. Lee, Takeshi Tokuyama, Takao Asano |
מוציא לאור | Springer Verlag |
עמודים | 271-280 |
מספר עמודים | 10 |
מסת"ב (מודפס) | 3540662006, 9783540662006 |
מזהי עצם דיגיטלי (DOIs) | |
סטטוס פרסום | פורסם - 1999 |
אירוע | 5th Annual International Conference on Computing and Combinatorics, COCOON 1999 - Tokyo, יפן משך הזמן: 26 יולי 1999 → 28 יולי 1999 |
סדרות פרסומים
שם | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
כרך | 1627 |
ISSN (מודפס) | 0302-9743 |
ISSN (אלקטרוני) | 1611-3349 |
כנס
כנס | 5th Annual International Conference on Computing and Combinatorics, COCOON 1999 |
---|---|
מדינה/אזור | יפן |
עיר | Tokyo |
תקופה | 26/07/99 → 28/07/99 |
הערה ביבליוגרפית
Publisher Copyright:© Springer-Verlag Berlin Heidelberg 1999.