Optimal Online Algorithms via Linear Scaling
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23
summary
Presents a simple linear scaling recipe: at time L solve the offline problem on the L/n fraction of items with capacities scaled by L/n, ignore past decisions, and use the fractional value as a randomized rounding probability for the current variable. Proves near-optimal ratios: 1−O(1/√K) for K-choice secretary, 1−ε for packing LPs when B = Ω((log D)/ε^2) matching lower bounds, and roughly 1/2−o(1/√γ) for temp-secretary with identical lengths, using binomial tail bounds and concentration.
AI-written summary · about