Technical Note—Online Hypergraph Matching with Delays
Marco Pavone, Amin Saberi, Maximilian Schiffer, Matt Wu Tsao
Abstract
Scheduling High-Capacity Shared Rides via Hypergraph Matchings Sharing economies, such as Uber Pool and Lyft Shared Saver, are becoming ubiquitous in modern transportation services. “Online Hypergraph Matching with Delays” by M. Pavone, A. Saberi, M. Schiffer, and M. Tsao studies an online hypergraph matching problem inspired by on-demand scheduling of shared rides in ridehailing systems. They formulate a ridesharing problem through a weighted hypergraph in which riders are represented by vertices and hyperedges and the associated weights represent the utility of serving the associated vertices groups of riders with a single vehicle. A ridesharing algorithm is, thus, a matching algorithm for the hypergraph. To model the on-demand nature of ridesharing, riders arrive sequentially and must either be quickly and irrevocably matched or discarded. In this work, the authors present a polynomial-time algorithm based on randomized batching and prove that it has the optimal worst-case performance.