User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse




Conference Paper

Weighted Flow Time does not Admit O(1)-competitive Algorithms


Chan,  Ho-Leung
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available

Bansal, N., & Chan, H.-L. (2009). Weighted Flow Time does not Admit O(1)-competitive Algorithms. In C. Mathieu (Ed.), Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 1238-1244). New York, NY: ACM. doi:10.1137/1.9781611973068.134.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-18ED-8
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 paper, we show an $\omega(1)$ lower bound on the competitive ratio of any deterministic online algorithm. Our result is based on a 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.