Technical Note—Greedy Algorithm for Multiway Matching with Bounded Regret
提出了一个统一模型，涵盖网络收益管理、按订单组装和在线随机装箱等在线匹配/分配问题，并给出一个简单的贪心算法，在非退化条件下实现有界或对数级遗憾。
A Unified View of Online Matching and Resource Allocation Problems Whereas small regret online algorithms for applications as diverse as network revenue management (NRM), assemble-to-order (ATO) systems, and online stochastic bin packing (SBP) are known in the literature, the design of the existing algorithms are tailored to the specific application and often use the strategy of resolving a planning linear program. In the paper “Greedy Algorithm for Multiway Matching with Bounded Regret,” Gupta proposes a unified model for studying such online matching/allocation problems. In the unified model, resources of three types—off-line (e.g., inventory in NRM), online-queueable (e.g., orders or resources in ATO systems), or online-nonqueueable (e.g., requests in NRM, items in SBP)—must be combined to create feasible configurations. Leveraging the unified framework, the author gives one simple greedy algorithm that gives small regret (bounded or logarithmic in time horizon) for these diverse applications under a mild nondegeneracy condition on the off-line planning problem.