Computational Complexity of Matching in Ride Sharing
summary
A formal model has vertices that stay for d steps and arrive in random order; a simple batching with batch size d+1 is analyzed by reducing competitive analysis to a graph-cover problem, using amplification gadgets and a computer-aided LP/dual search for small d (tested up to d≈50), yielding a proven bound of about competitive ratio 0.279 (1/3.58) and a universal impossibility that no algorithm exceeds 0.5. Against adversarial arrivals a randomized online scheme gives 1/4, and a ride‑matching variant is shown PSPACE‑complete while Euclidean compatibility admits a PTAS.
AI-written summary · about
chapters (13)
- 0:00Intro
- 1:05Matching is the most central problem in algorithm design
- 2:29Online Matching with Deadlines
- 10:23Proof Outline
- 16:28Reduction to a graph-covering problem
- 20:26LP based proof
- 24:41Second model: adversarial order
- 26:13Three ideas
- 28:33Description of the Algorithm
- 29:21A few open problems
- 30:17Online Stochastic Matching
- 33:06Ride Matching
- 35:36Concluding Remarks
related talks
33mThe Rideshare Dispatch Problem (Aka Online Bipartite Matching with Supply Externalities)
01h 38mRidesharing
50mDiversity in Matching Markets
32mDynamic Matching Models
36mThe Intractability of Hylland-Zeckhauser and its Aftermath
29mClearing Matching Markets Efficiently: Informative Signals and Match Recommendations
41mDynamic Pricing in Ride-Sharing Platforms
44mOnline Advertisements and Online Algorithms