Competitive Algorithms from Competitive Equilibria
Talkat Optimization and Decision-Making Under Uncertainty (Simons Institute, September 2016) · 2016-09-19..09-23
summary
Online non‑clairvoyant scheduling over a general packing polytope is modeled, and the rule that maximizes the product of job rates — proportional fairness — is proposed as a single, non‑clairvoyant policy. It achieves constant‑competitive total completion time (no speedup), and with constant resource augmentation it gives constant competitive flow time for monotone cases (polymatroids, CES/substitute utilities). A familiar fairness rule (DRF) has an Ω(√D) blowup on a constructed D‑dimensional instance, and no constant competitive flow‑time algorithm exists for the full generality without super‑constant speed.
AI-written summary · about
chapters (28)
- 0:00Start
- 0:26Single Machine Scheduling • Single machine
- 1:11Scheduling Policy
- 1:53Constraints on Policy
- 2:56Total Delay Objectives
- 3:49Competitive Analysis
- 5:48LP Formulation
- 7:26Packing Scheduling Problem (PSP)
- 10:00Unrelated Machine Scheduling
- 11:07Packing constraints at time t
- 11:47Overall Problem
- 12:10Multidimensional Scheduling
- 13:13Practical Motivation
- 14:19Common Utility Functions • Leontief: Rate of processing depends on bottleneck resource
- 19:12Some Intuition
- 20:09Multi-dimensional Example
- 21:01Max-Min Fairness (MMF)
- 21:46MMF (or DRF) Allocation
- 22:47Optimal Allocation
- 23:53Proportional Fairness (PF)
- 24:33PF as Market Clearing
- 27:32Subclasses for Flow Time
- 31:13Optimality Condition of PF
- 32:41Main Idea: Prefix Fairness
- 34:20Proof Sketch
- 36:16Analysis for Flow Time
- 36:53Lag of PF w.r.t. Optimum
- 37:49Potential Function