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 preemptive schedule on a minimum number of machines. Our main result is a general O(log m)-competitive algorithm for the online problem, where m is the optimal number of machines used in an offline solution.
This is the first improvement on an intriguing problem in nearly two decades. To date, the best known result is a O(log (p_{max}/p_{min}))-competitive algorithm by Phillips et al. (STOC~1997) that depends on the ratio of maximum and minimum job sizes, p_{max} and p_{min}. Even for m=2 no better algorithm was known. Our algorithm is in this case constant-competitive.
If, however, migration is not allowed, we show that there is no f(m)-competitive algorithm for machine minimization for any function f. This strongly contrasts known results for related problems, where migration and non-migration causes only O(1) difference in competitive ratio.
This is a joint work with Megow and Schewior (SODA’16 & SPAA’16).
Time
2016-07-08 10:00 ~ 11:00Speaker
Lin Chen,MTA SZTAKI （Hungarian Academy of Science）Room
Room 308, No.100 Wudong Road, School of Information Management & Engineering, Shanghai University of Finance & Economics
