| Presentation | 2007-04-26 Scheduling with Conflicts: Approximation Algorithms and Online Algorithms Guy Evan, Magnus M. Halldorsson, Lotem Kaplan, Dana Ron, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | We consider the following problem of scheduling with conflicts (SWC). Find a minimum makespan schedule on identical machines where conflicting jobs may not be scheduled concurrently. We present the first approximation algorithms for the case in which conflicts between jobs are modeled general graphs both for unit jobs and jobs with arbitrary processing times. We also consider an online model in which each job has a release time. We present the first results fo SWC in the online model, including lower and upper bounds for the competitive ratio of deterministic online algorithms. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | |
| Paper # | COMP2007-3 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2007/4/19(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | ENG |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | Scheduling with Conflicts: Approximation Algorithms and Online Algorithms |
| Sub Title (in English) | |
| Keyword(1) | |
| 1st Author's Name | Guy Evan |
| 1st Author's Affiliation | School of Electrical Engineering, Tel-Aviv Univ.() |
| 2nd Author's Name | Magnus M. Halldorsson |
| 2nd Author's Affiliation | Dept. of Computer Science, Faculty of Engineering, University of Iceland |
| 3rd Author's Name | Lotem Kaplan |
| 3rd Author's Affiliation | School of Electrical Engineering, Tel-Aviv Univ. |
| 4th Author's Name | Dana Ron |
| 4th Author's Affiliation | School of Electrical Engineering, Tel-Aviv Univ. |
| Date | 2007-04-26 |
| Paper # | COMP2007-3 |
| Volume (vol) | vol.107 |
| Number (no) | 24 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |