Matching Drivers to Riders: A Two-Stage Robust Approach

References

• Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1253–1264.Google Scholar
• Arora S, Hazan E, Kale S (2012) The multiplicative weights update method: A meta-algorithm and applications. Theory Comput. 8(1):121–164.Crossref, Google Scholar
• Atamtürk A, Zhang M (2007) Two-stage robust network flow and design under demand uncertainty. Oper. Res. 55(4):662–673.Link, Google Scholar
• Bansal N, Buchbinder N, Gupta A, Naor JS (2007) An o(logk2)-competitive algorithm for metric bipartite matching. Eur. Sympos. Algorithms (Springer, Berlin), 522–533.Google Scholar
• Baron O, Milner J, Naseraldin H (2011) Facility location: A robust optimization approach. Production Oper. Management 20(5):772–785.Crossref, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Jaillet P, Martin S (2019) Online vehicle routing: The edge of optimization in large-scale applications. Oper. Res. 67(1):143–162.Link, Google Scholar
• Birnbaum B, Mathieu C (2008) On-line bipartite matching made simple. ACM SIGACT News 39(1):80–87.Crossref, Google Scholar
• Bose P, Maheshwari A, Narasimhan G, Smid M, Zeh N (2004) Approximating geometric bottleneck shortest paths. Comput. Geometry 29(3):233–249.Crossref, Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Eur. Sympos. Algorithms (Springer, Berlin), 253–264.Google Scholar
• Cheng B, Qian S, Cao J, Xue G, Yu J, Zhu Y, Li M, Zhang T (2019) STL: Online detection of taxi trajectory anomaly based on spatial-temporal laws. Internat. Conf. Database Systems Adv. Appl. (Springer, Berlin), 764–779.Google Scholar
• Devanur NR, Hayes TP (2009) The AdWords problem: Online keyword matching with budgeted bidders under random permutations. Proc. 10th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 71–78.Google Scholar
• Devanur NR, Jain K, Kleinberg RD (2013) Randomized primal-dual analysis of ranking for online bipartite matching. Proc. 24th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 101–107.Google Scholar
• Dhamdhere K, Goyal V, Ravi R, Singh M (2005) How to pay, come what may: Approximation algorithms for demand-robust covering problems. 46th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 367–376.Google Scholar
• El Housni O, Goyal V (2017) Beyond worst-case: A probabilistic analysis of affine policies in dynamic optimization. Adv. Neural Inform. Processing Systems (Curran Associates Inc., Red Hook, NY), 4756–4764.Google Scholar
• El Housni O, Goyal V (2021) On the optimality of affine policies for budgeted uncertainty sets. Math. Oper. Res. 46(2):674–711.Link, Google Scholar
• El Housni O, Foussoul A, Goyal V (2024) LP-based approximations for disjoint bilinear and two-stage adjustable robust optimization. Math. Programming 206(1):239–281.Crossref, Google Scholar
• El Housni O, Goyal V, Shmoys D (2021) On the power of static assignment policies for robust facility location problems. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin), 252–267.Google Scholar
• Escoffier B, Gourvès L, Monnot J, Spanjaard O (2010) Two-stage stochastic matching and spanning tree problems: Polynomial instances and approximation. Eur. J. Oper. Res. 205(1):19–30.Crossref, Google Scholar
• Feige U, Jain K, Mahdian M, Mirrokni V (2007) Robust combinatorial optimization with exponential scenarios. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin), 439–453.Google Scholar
• Feldman M, Svensson O, Zenklusen R (2016) Online contention resolution schemes. Proc. 27th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1014–1033.Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. 50th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE, Piscataway, NJ), 117–126.Google Scholar
• Feng Y, Niazadeh R (2020) Batching and optimal multi-stage bipartite allocations. Chicago Booth Research Paper 20–29, University of Chicago Booth School of Business, IL.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2021) Two-stage stochastic matching with application to ride hailing. Proc. 2021 ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 2862–2877.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2023) Two-stage stochastic matching and pricing with applications to ride hailing. Oper. Res. 72(4):1574–1594.Link, Google Scholar
• Gabow HN, Tarjan RE (1988) Algorithms for two bottleneck optimization problems. J. Algorithms 9(3):411–417.Crossref, Google Scholar
• Garfinkel RS, Gilbert K (1978) The bottleneck traveling salesman problem: Algorithms and probabilistic analysis. J. ACM 25(3):435–448.Crossref, Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. Proc. Nineteenth Annual ACM-SIAM Sympos. Discrete Algorithms, vol. 8 (SODA, San Francisco), 982–991.Google Scholar
• Goyal D, Jaiswal R (2023) Tight FPT approximation for constrained k-center and k-supplier. Theoret. Comput. Sci. 940:190–208.Crossref, Google Scholar
• Grüne C, Wulf L (2025) Completeness in the polynomial hierarchy for many natural problems in bilevel and robust optimization. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin), 256–269.Google Scholar
• Gupta A, Nagarajan V, Ravi R (2010) Thresholded covering algorithms for robust and max-min optimization. Internat. Colloquium Automata Languages Programming (Springer, Berlin), 262–274.Crossref, Google Scholar
• Haeupler B, Mirrokni VS, Zadimoghaddam M (2011) Online stochastic weighted matching: Improved approximation algorithms. Internat. Workshop Internet Network Econom. (Springer, Berlin), 170–181.Crossref, Google Scholar
• Hochbaum DS, Shmoys DB (1986) A unified approach to approximation algorithms for bottleneck problems. J. ACM 33(3):533–550.Crossref, Google Scholar
• Jaillet P, Lu X (2014) Online stochastic matching: New algorithms with better bounds. Math. Oper. Res. 39(3):624–646.Link, Google Scholar
• Kaibel V, Peinhardt M (2006) On the Bottleneck Shortest Path Problem (Konrad-Zuse-Zentrum fur Informationstechnik Berlin, Berlin), 1–9.Google Scholar
• Kalyanasundaram B, Pruhs K (1993) Online weighted matching. J. Algorithms 14(3):478–488.Crossref, Google Scholar
• Karande C, Mehta A, Tripathi P (2011) Online bipartite matching with unknown distributions. Proc. 43rd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 587–596.Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 352–358.Google Scholar
• Katriel I, Kenyon-Mathieu C, Upfal E (2008) Commitment under uncertainty: Two-stage stochastic matching problems. Theoret. Comput. Sci. 408(2–3):213–223.Crossref, Google Scholar
• Khuller S, Mitchell SG, Vazirani VV (1994) On-line algorithms for weighted bipartite matching and stable marriages. Theoret. Comput. Sci. 127(2):255–267.Crossref, Google Scholar
• Kong N, Schaefer AJ (2006) A factor 12 approximation algorithm for two-stage stochastic matching problems. Eur. J. Oper. Res. 172(3):740–746.Crossref, Google Scholar
• Korula N, Pál M (2009) Algorithms for secretary problems on graphs and hypergraphs. Internat. Colloquium Automata Languages Programming (Springer, Berlin), 508–520.Crossref, Google Scholar
• Lee E, Singla S (2017) Maximum matching in the online batch-arrival model. Internat. Conf. Integer Programming Combin. Optim. (Springer, Berlin), 355–367.Google Scholar
• Lyft (2016) Matchmaking in Lyft line—Part 1. https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4.Google Scholar
• Manshadi VH, Gharan SO, Saberi A (2012) Online stochastic matching: Online actions based on offline statistics. Math. Oper. Res. 37(4):559–573.Link, Google Scholar
• Matuschke J, Schmidt-Kraepelin U, Verschae J (2019) Maintaining perfect matchings at low cost. 46th Internat. Colloquium Automata, Languages, Programming (ICALP 2019), vol. 132 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• Mehta A (2013) Online matching and ad allocation. Foundations and Trends Theoret. Comput. Sci. 8(4):265–368.Google Scholar
• Mehta A, Waggoner B, Zadimoghaddam M (2014) Online stochastic matching with unequal probabilities. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1388–1404.Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) AdWords and generalized online matching. J. ACM 54(5):22.Crossref, Google Scholar
• Meyerson A, Nanavati A, Poplawski L (2006) Randomized online algorithms for minimum metric bipartite matching. Proc. 17th Annual ACM-SIAM Sympos. Discrete Algorithm (Society for Industrial and Applied Mathematics, Miami), 954–959.Google Scholar
• Plotkin S, Shmoys DB, Tardos É (1995) Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20(2):257–301.Link, Google Scholar
• Raghvendra S (2016) A robust and optimal online algorithm for minimum metric bipartite matching. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Wadern, Germany), 1–18.Google Scholar
• Uber (2020) Uber marketplace and matching. https://marketplace.uber.com/matching.Google Scholar
• Zhang L, Hu T, Min Y, Wu G, Zhang J, Feng P, Gong P, Ye J (2017) A taxi order dispatch model based on combinatorial optimization. Proc. 23rd ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 2151–2159.Google Scholar