On the online machine minimization problem (Lin Chen)


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).


2016-07-08  10:00 ~ 11:00   


Lin Chen,MTA SZTAKI (Hungarian Academy of Science)


Room 308, No.100 Wudong Road, School of Information Management & Engineering, Shanghai University of Finance & Economics