Online Hypergraph Matching with Delays

• 成果类型: Article
• 署名作者: Pavone, Marco; Saberi, Amin; Schiffer, Maximilian; Tsao, Matt Wu
• 署名单位: Stanford University; Stanford University; Technical University of Munich; Technical University of Munich; Stanford University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2277
• 发表日期: 2022

摘要

We study an online hypergraph matching problem inspired by ridesharing and delivery applications. The vertices of a hypergraph are revealed sequentially and must be matched shortly thereafter, otherwise they will leave the system in favor of an outside option. Hyperedges are revealed to the algorithm once all of its vertices have arrived, and can only be included into the matching before any of its vertices leave the system. The cardinality of hyperedges are bounded by a small constant which represents the capacity of service vehicles. We study utility maximization and cost minimization objectives in this model. In the utility maximization setting, we present a polynomial time algorithm which provably achieves the optimal competitive ratio provided that the vehicle capacity is at least 3. For the cost minimization setting, we assume costs are monotone, which is a natural assumption in ridesharing and delivery problems. When the vehicle capacity is 2, we present a polynomial-time thresholding algorithm and prove that it has the optimal competitive ratio among deterministic algorithms. For higher vehicle capacities, we show that the performance of a randomized batching algorithm is within a small constant of the optimal competitive ratio achievable in polynomial time.