Flow Time Scheduling with Uncertain Processing Time
summary
Presents competitive guarantees when job sizes are only estimated: an distortion-oblivious deterministic algorithm for unweighted flow time with competitive ratio about mu log mu and a nearly matching lower bound; weighted flow time requires knowing an upper bound on the distortion and gets algorithms with costs like mu^2 log W (or mu^3 log_mu P variants). Core technique is an approximate-sort structure using full/partial bins (LIFO processing per partial bin) and weight classes; open problem is weighted distortion-oblivious.
AI-written summary · about
chapters (14)
- 0:00Introduction
- 3:11The problem
- 5:33Optimal online algorithm
- 10:15Measuring accuracy
- 13:10Do we know the Distortion
- 16:33Results
- 22:53Summary
- 23:41Distortion oblivious algorithm
- 29:47Defining the algorithm
- 30:41Unweighted algorithm
- 35:34Processing
- 38:44Weighted Case
- 41:44Unweighted Case
- 46:14Conclusions
related talks
35mApproximation hardness and online algorithms for resource scheduling
16mMinFlow: High-performance and Cost-efficient Data Passing for I/O-intensive Stateful...
40mEverything Will Flow
25mApproximating Fair Queueing on Reconfigurable Switches
19mLook Before, Before You Leap: Online Vector Load Balancing with Few Reassignments
46mIntro: Scheduling SIG
19mDistributed load balancing: a new framework and improved guarantees
17mSolving Max-Min Fair Resource Allocations Quickly on Large Graphs