Competitive Analysis Meets Stochastic Input: Secretary Problems And Prophet Inequalities
summary
Algorithms assume a partly adversarial, partly stochastic input and give concrete, constant-factor guarantees: a single threshold yields a 2-approx for single-item prophet inequalities; K-unit gets 1−O(1/√K) and can be tuned for small K; matching and other packing problems obtain constant ratios via an online contention resolution scheme (OCRS). For allocation, setting per-item balanced prices at half the expected contribution gives a 2-approx; alternatives include dual-learning from samples and a primal “best-effort” rounding that also provably works.
AI-written summary · about
chapters (10)
- 0:00Motivating online problems
- 3:38Semi-random model overview
- 8:03Defining selection problems
- 11:56Benchmarking with hindsight
- 14:06Profit inequality techniques
- 27:34Online matching algorithms
- 31:05Online contention resolution
- 36:23Balanced thresholds
- 49:25Resource allocation strategies
- 59:06Secretary problem and research
related talks
48mSecretary Problems and Online Selection with A Priori Information
43mLearning about Auctions
33mRobust Algorithms for Secretaries and Bandits
40mApproximation Algorithms for Optimization under Uncertainty
29mIndividual Fairness in Advertising Auctions through Inverse Proportionality
48mOutposts Between Worst- and Average Case Analysis: A Case Study in Auction Design
34mPandora's Box with Correlations: Learning and Approximation
01h 08mData Driven Optimization Models and Algorithms