Online Matching for Ride-sharing
summary
A new fully online matching model lets every request arrive and expire with deadlines and overlapping time windows, capturing ride‑sharing pairings on general (nonbipartite) graphs. The paper shows the randomized ranking beats 0.5 guarantee still holds in this model, pins ranking at about 0.567 on bipartite instances, and proves no algorithm reaches 1−1/e here. Key tools are a novel gain‑sharing analysis with an active/passive and victim/compensation concept; a separate fixed‑window reduction yields a 0.25 competitive algorithm for edge‑weighted cases.
AI-written summary · about