Technical Note-Online Hypergraph Matching with Delays

Marco Pavone, Amin Saberi, Maximilian Schiffer, Matt Wu Tsao

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

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 theywill leave the systemin favor of an outside option. Hyperedges are revealed to the algorithmonce 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 constantwhich 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.

Original languageEnglish
Pages (from-to)2194-2212
Number of pages19
JournalOperations Research
Volume70
Issue number4
DOIs
StatePublished - 1 Jul 2022

Keywords

  • competitive analysis
  • matching
  • online algorithms

Fingerprint

Dive into the research topics of 'Technical Note-Online Hypergraph Matching with Delays'. Together they form a unique fingerprint.

Cite this