Edge-Weighted Online Windowed Matching

• 成果类型: Article
• 署名作者: Ashlagi, Itai; Burq, Maximilien; Dutta, Chinmoy; Jaillet, Patrick; Saberi, Amin; Sholley, Chris
• 署名单位: Stanford University; Massachusetts Institute of Technology (MIT)
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2022.1289
• 发表日期: 2023
• 页码: 999-1016
• 关键词: algorithms

摘要

Consider amatching problem, in which agents arrive to amarketplace over time and leave after some time periods. Agents can only bematchedwhile present in themarketplace. Each pair of agents can yield a different match value, and a social planner seeks to maximize the total value from matches over a finite time horizon. First we study the case in which vertices arrive in an adversarial order. For the case when agents depart in the order of arrival, we provide a randomized 1/4-competitive algorithm. When departure times are drawn independently from a distribution with nondecreasing hazard rate, we establish a 1/8-competitive algorithm. When the arrival order is chosen uniformly at random and agents leave after a fixed number of time periods, a batching algorithm, which computes a maximum-weighted matching periodically, is shown to be 0.279-competitive.