Name
Abstract | ||
|---|---|---|
We consider the online machine minimization problem in which jobs with hard deadlines arrive online over time at their release dates. The task is to determine a feasible schedule on a minimum number of machines. Our main result is a general O(m^2 log m)-competitive algorithm for the preemptive online problem, where m is the optimal number of machines used in an offline solution. This is the first improvement on an O(log (p_max/p_min))-competitive algorithm by Phillips et al. (STOC 1997), which was to date the best known algorithm even when m=2. Our algorithm is O(1)-competitive for any m that is bounded by a constant. To develop the algorithm, we investigate two complementary special cases of the problem, namely, laminar instances and agreeable instances, for which we provide an O(log m)-competitive and an O(1)-competitive algorithm, respectively. Our O(1)-competitive algorithm for agreeable instances actually produces a non-preemptive schedule, which is of its own interest as there exists a strong lower bound of n, the number of jobs, for the general non-preemptive online machine minimization problem by Saha (FSTTCS 2013), which even holds for laminar instances. |
Year | Venue | Field |
|---|---|---|
2015 | CoRR | Minimization problem,Mathematical optimization,Upper and lower bounds,Computer science,Algorithm,Competitive algorithm,Minification,Competitive analysis |
DocType | Volume | Citations |
Journal | abs/1506.05721 | 2 |
PageRank | References | Authors |
0.37 | 0 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Lin Chen | 1 | 100 | 23.63 |
| nicole megow | 2 | 302 | 26.73 |
| Kevin Schewior | 3 | 37 | 9.79 |