Online Flow-Time Optimization
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23
summary
Online flow-time on unrelated machines gets two concrete algorithms, one clairvoyant greedy that assigns each arrival to the machine minimizing the SRPT-induced increase and is (1+ε)-speed, 1/ε competitive, and one selfish migrate non‑clairvoyant scheme that uses round‑robin on machines, lets jobs migrate to maximize a virtual-rate proxy, requires migrations but bounds them, and achieves (1+ε)-speed, about 1/ε^2 competitive. Analysis uses LP duality/dual‑fitting, a potential/Nash‑equilibrium argument, and proves monotone virtual rates so the bounds hold.
AI-written summary · about