Fully Online Matching with General Stochastic Arrivals and Departures
针对网约车等动态匹配场景，提出一种基于线性规划的在线算法，在参与者随机到达和离开时保证至少0.192的竞争比，比现有最优结果提升50%以上。
A Novel Fully Online Matching Algorithm in Stochastic Environments In many modern applications, such as ride-sharing, participants arrive and depart dynamically, requiring quick decisions about who to match and when. In “Fully Online Matching with General Stochastic Arrivals and Departures,” Li, Wang, and Yan introduce a fully online matching framework that models these real-world dynamics. Each arrival follows a known identical and independent distribution over agent types, whereas the sojourn time is unknown in advance and follows type-specific distributions with known expectations. To address this, they propose a linear programming–based algorithm that guarantees a competitive ratio of at least 0.192 under mild conditions—more than 50% better than the state-of-the-art result of 0.125. They also establish several hardness results to highlight the intrinsic difficulty of the problem. Numerical experiments further confirm the effectiveness and efficiency of their algorithm, offering new insights for decision making in stochastic and dynamic environments.