Batching and Optimal Multi-stage Bipartite Allocations

on YouTube ↗24m

" summary

A polynomial-time algorithm achieves the optimal competitive ratio for K-stage bipartite allocation, namely gamma_K = 1 - (1-1/K)^K (tending to 1-1/e), and a matching lower bound shows no algorithm can do better. The method solves a sequence of convex programs with a convex regularizer via backward recursion that hedges between stages, uses a graph decomposition (matching-skeleton) and primal–dual dual-fitting to analyze guarantees, and extends to fractional solutions and integral solutions under large-budget assumptions.

AI-written summary · about

" chapters (13)

1. 0:00Northwestern ENGINEERING
2. 1:36Batching inefficiency tradeoff
3. 2:44Revisiting Classic Models on Online Bipartite Allocations
4. 6:00Worst-case Competitive Analysis
5. 10:21Hedging is Necessary
6. 12:45Regularized Max-weight Matching Convex Program
7. 13:42Re-inventing a Wheel
8. 15:36Sequence of Polynomials of Decreasing Degrees
9. 16:39Putting Pieces Together: Final Algorithm
10. 17:31Primal and Dual LPs of Max-Weight Matching
11. 18:36Structural Decomposition Lemma
12. 22:30Summary
13. 22:51Open Problems