Technical Note—Online Hypergraph Matching with Delays

Marco Pavone (), Amin Saberi (), Maximilian Schiffer () and Matt Wu Tsao ()
Additional contact information
Marco Pavone: Department of Aeronautics & Astronautics, Stanford University, Stanford, California 94305
Amin Saberi: Department of Management Science and Engineering, Stanford University, Stanford, California 94305
Maximilian Schiffer: TUM School of Management & Munich Data Science Institute, Technical University of Munich, Munich 80333, Germany
Matt Wu Tsao: Department of Electrical Engineering, Stanford University, Stanford, California 94305

Operations Research, 2022, vol. 70, issue 4, 2194-2212

Abstract: 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.

Keywords: Market Analytics and Revenue Management; online algorithms; competitive analysis; matching (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2277 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:4:p:2194-2212

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().