上财陆品燕教授获颁第八届世界华人数学家大会ICCM数学银奖

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:00   

Speaker

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