Modern Primal–Dual Frameworks for Prior-Free Online Resource Allocation
Abstract
Linear-programming (LP)–based primal–dual methods are fundamental for designing and analyzing algorithms in adversarial (prior-free) online resource allocation. This chapter provides a tutorial on two modern primal–dual frameworks, emphasizing recent developments and contemporary models in operations research. Part I develops an LP-based convex-programming framework where solving a regularized convex program at each arrival captures the trade-off between greediness and hedging, yielding a dual certificate via Karush–Kuhn–Tucker conditions. Because standard LP relaxations can be weak or intractable for stochastic outcomes, Part II introduces a complementary LP-free framework that provides a universal certificate system for evaluating competitive ratios under such uncertainty. Covering a wide array of models—including online vertex-weighted bipartite matching, edge-weighted online matching with free disposal, online matching with stochastic rewards, reusable resources, two-sided assortment optimization, configuration allocation (whole-page optimization), AdWords, and costly cancellations—the tutorial equips readers with versatile proof templates to analyze existing algorithms and develop new solutions for emerging applications.
Funding: R. Niazadeh is supported by grants from the University of Chicago Booth School of Business. R. Udwani is supported by the National Science Foundation, Division of Civil, Mechanical and Manufacturing Innovation [Grant 2340306].
Supplemental Material: The electronic companion is available at https://doi.org/10.1287/educ.2026.0304.
Your Access Options
-
Login Options
Purchase Options
Save for laterOther Options
Token AccessClaim access using a tokenRestore guest accessApplies for purchases made as a guest
