Greedy Algorithm for Multiway Matching with Bounded Regret
成果类型：
Article
署名作者：
Gupta, Varun
署名单位：
University of Chicago
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.2022.2400
发表日期：
2024
页码：
1139-1155
关键词：
摘要：
In this paper, we prove the efficacy of a simple greedy algorithm for a finite horizon online resource allocation/matching problem when the corresponding static planning linear program (SPP) exhibits a nondegeneracy condition called the general position gap (GPG). The key intuition that we formalize is that the solution of the reward-maximizing SPP is the same as a feasibility linear program restricted to the optimal basic activities, and under GPG, this solution can be tracked with bounded regret by a greedy algorithm, that is, without the commonly used technique of periodically resolving the SPP. The goal of the decision maker is to combine resources (from a finite set of resource types) into configurations (from a finite set of feasible configurations) in which each configuration is specified by the number of resources consumed of each type and a reward. The resources are further subdivided into three types-off-line (whose quantity is known and available at time 0), online-queueable (which arrive online and can be stored in a buffer), and onlinenonqueueable (which arrive online and must be matched on arrival or lost). Under GPG, we prove that (i) our greedy algorithm gets bounded anytime regret of O(1/e0) for matching reward (e0 is a measure of the GPG) when no configuration contains both an onlinequeueable and an online-nonqueueable resource and (ii) O(log t) expected anytime regret otherwise (we also prove a matching lower bound). By considering the three types of resources, our matching framework encompasses several well-studied problems, such as dynamic multisided matching, network revenue management, online stochastic packing, and multiclass queueing systems.