Modern Primal-Dual Frameworks for Prior-Free Online Resource Allocation
For researchers and practitioners in online algorithms and operations research, this tutorial offers systematic frameworks to analyze competitive ratios and develop new algorithms for a wide range of resource allocation problems.
This tutorial presents two modern primal-dual frameworks for prior-free online resource allocation, covering models like online matching, AdWords, and configuration allocation. It provides proof templates to analyze and design algorithms, demonstrating broad applicability across operations research problems.
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 tradeoff between greediness and hedging, yielding a dual certificate via Karush-Kuhn-Tucker (KKT) 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.