Weighted flow time does not admit O(1)-competitive algorithms

N. Bansal; H.L. Chan

doi:10.1145/1496770.1496904

Weighted flow time does not admit O(1)-competitive algorithms

N. Bansal, H.L. Chan

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

44 Citations (Scopus)

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 rj, weight wj and size pj, 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 ¿(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.

Original language	English
Title of host publication	Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09, New York NY, USA, January 4-6, 2009)
Editors	C. Mathieu
Place of Publication	New York
Publisher	Association for Computing Machinery, Inc
Pages	1238-1244
DOIs	https://doi.org/10.1145/1496770.1496904
Publication status	Published - 2009

Access to Document

10.1145/1496770.1496904

Cite this

@inproceedings{826850c1f82142e1a6f03ed575b89e20,

title = "Weighted flow time does not admit O(1)-competitive algorithms",

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 rj, weight wj and size pj, 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 ¿(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.",

author = "N. Bansal and H.L. Chan",

year = "2009",

doi = "10.1145/1496770.1496904",

language = "English",

pages = "1238--1244",

editor = "C. Mathieu",

booktitle = "Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09, New York NY, USA, January 4-6, 2009)",

publisher = "Association for Computing Machinery, Inc",

address = "United States",

}

Weighted flow time does not admit O(1)-competitive algorithms. / Bansal, N.; Chan, H.L.
Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09, New York NY, USA, January 4-6, 2009). ed. / C. Mathieu. New York: Association for Computing Machinery, Inc, 2009. p. 1238-1244.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Weighted flow time does not admit O(1)-competitive algorithms

AU - Bansal, N.

AU - Chan, H.L.

PY - 2009

Y1 - 2009

N2 - 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 rj, weight wj and size pj, 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 ¿(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.

AB - 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 rj, weight wj and size pj, 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 ¿(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.

UR - http://doi.acm.org/10.1145/1496770.1496904

U2 - 10.1145/1496770.1496904

DO - 10.1145/1496770.1496904

M3 - Conference contribution

SP - 1238

EP - 1244

BT - Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09, New York NY, USA, January 4-6, 2009)

A2 - Mathieu, C.

PB - Association for Computing Machinery, Inc

CY - New York

ER -

Weighted flow time does not admit O(1)-competitive algorithms

Abstract

Access to Document

Other files and links

Fingerprint

Cite this