AG 1, AG 3, AG 5, RG2, AG 2, AG 4, RG1, SWS   Info

AG Audience

English

30 Minutes

Saarbrücken

We consider the classic online scheduling problem of minimizing the total weighted flow time on a single machine with preemptions. Here, each job $j$ has an arbitrary arrival time $r_j$, weight $w_j$ and size $p_j$, and given a schedule its flow time is defined as the duration of time since its arrival until it completes its service requirement. The first non-trivial algorithms with poly-logarithmic competitive ratio for this problem were obtained relatively recently, and it was widely believed that the problem admits a constant factor competitive algorithm. In this talk, we show an $\omega(1)$ lower bound on the competitive ratio of any deterministic online algorithm. Our result is based on a novel gap amplification technique for online algorithms. Starting with a trivial lower bound of 1, we give a procedure to improve the lower bound sequentially, while ensuring at each step that the size of the instance increases relatively modestly. This is a joint work with Nikhil Bansal.

Ho-Leung Chan

112

--email hidden

passcode not visible

logged in users only

Online algorithms, competitive analysis, weighted flow time