Fully Online Matching with General Stochastic Arrivals and Departures

• 成果类型: Article; Early Access
• 署名作者: Li, Zihao; Wang, Hao; Yan, Zhenzhen
• 署名单位: National University of Singapore; Chinese Academy of Sciences; University of Science & Technology of China, CAS; Nanyang Technological University; Nanyang Technological University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2023.0190
• 发表日期: 2025-11-10
• 关键词: fully online matching; Randomized algorithm; competitive ratio

摘要

We study a fully online matching problem with general stochastic arrivals and departures. In this model, each online arrival follows a known identical and independent distribution over a fixed set of agent types. Its sojourn time is unknown in advance and follows type-specific distributions with known expectations. The goal is to maximize the weighted reward from successful matches. To solve this problem, we propose a linear program (LP)-based algorithm whose competitive ratio is lower bounded by 0.192 under mild conditions. To demonstrate the challenges of the problem, we further establish several hardness results. In particular, we show that no online algorithm can achieve a competitive ratio better than 1/2 in this model, and if using our LP as a benchmark for competitive ratio analysis, no algorithm can achieve a better ratio than 1/3. When no assumptions are made regarding the sojourn time distributions, we demonstrate that it is impossible to achieve a positive competitive ratio for the general case using our LP as a benchmark for competitive ratio analysis. We further extend our model to accommodate general sojourn times under Poisson arrivals and demonstrate a better competitive ratio compared with state-of-the-art results derived under Poisson arrivals and departures, a special case of our general settings. Finally, we demonstrate the effectiveness and efficiency of our algorithm numerically.