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

Bansal, Nikhil; Chan, Ho-Leung

doi:10.1137/1.9781611973068.134

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Conference Paper

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

MPS-Authors

/persons/resource/persons44228

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

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

Supplementary Material (public)

There is no public supplementary material available

Citation

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: https://hdl.handle.net/11858/00-001M-0000-000F-18ED-8

Abstract

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.