Batching and Optimal Multistage Bipartite Allocations

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 (Society for Industrial and Applied Mathematics, Philadelphia), 1253–1264.Google Scholar
• Agrawal S, Devanur NR (2014) Fast algorithms for online stochastic convex programming. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1405–1424.Google Scholar
• Agrawal S, Zadimoghaddam M, Mirrokni V (2018) Proportional allocation: Simple, distributed, and diverse matching with high entropy. Internat. Conf. Machine Learning (PMLR, New York), 99–108.Google Scholar
• Alaei S, Makhdoumi A, Malekian A, Pekeč S (2022) Revenue-sharing allocation strategies for two-sided media platforms: Pro-rata vs. user-centric. Management Sci. 68(12):8699–8721.Link, Google Scholar
• Albers S, Passen A (2019) New online algorithms for story scheduling in web advertising. Algorithmica 81(1):1–25.Crossref, Google Scholar
• Amazon Web Services (2021) AWS batch FAQs. Accessed August 1, 2021, https://aws.amazon.com/batch/faqs/.Google Scholar
• Aouad A, Saban D (2021) Online assortment optimization for two-sided matching platforms. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 91–92.Google Scholar
• Aouad A, Saritaç Ö (2020) Dynamic stochastic matching under limited time. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 789–790.Google Scholar
• Arnosti N, Johari R, Kanoria Y (2021) Managing congestion in matching markets. Manufacturing Service Oper. Management 23(3):620–636.Link, Google Scholar
• Ashlagi I, Burq M, Dutta C, Jaillet P, Saberi A, Sholley C (2019) Edge weighted online windowed matching. Proc. 2019 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 729–742.Google Scholar
• Ata B, Barjesteh N, Kumar S (2020) Dynamic dispatch and centralized relocation of cars in ride-hailing platforms. Preprint, submitted September 14, http://dx.doi.org/10.2139/ssrn.3675888.Google Scholar
• Aveklouris A, DeValve L, Ward AR, Wu X (2021) Matching impatient and heterogeneous demand and supply. Preprint, submitted February 4, https://arxiv.org/abs/2102.02710.Google Scholar
• Backstrom L, Kleinberg J, Kumar R (2009) Optimizing web traffic via the media scheduling problem. Proc. 15th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 89–98.Google Scholar
• Bahmani B, Kapralov M (2010) Improved bounds for online stochastic matching. de Berg M, Meyer U, eds. Algorithms–ESA 2010, Lecture Notes in Computer Science, vol. 6346 (Springer, Berlin, Heidelberg), 170–181.Google Scholar
• Balseiro S, Lu H, Mirrokni V (2021) Regularized online allocation problems: Fairness and beyond. Internat. Conf. Machine Learning (PMLR, New York), 630–639.Google Scholar
• Balseiro SR, Lu H, Mirrokni V (2022) The best of many worlds: Dual mirror descent for online allocation problems. Oper. Res. 71(1):101–119.Link, Google Scholar
• Balseiro SR, Feldman J, Mirrokni V, Muthukrishnan S (2014) Yield optimization of display advertising with ad exchange. Management Sci. 60(12):2886–2907.Link, Google Scholar
• Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev. 53(3):464–501.Crossref, Google Scholar
• Bertsimas D, Iancu DA, Parrilo PA (2010) Optimality of affine policies in multistage robust optimization. Math. Oper. Res. 35(2):363–394.Link, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming (Springer Science & Business Media, New York).Crossref, Google Scholar
• Birnbaum B, Mathieu C (2008) On-line bipartite matching made simple. ACM SIGACT News 39(1):80–87.Crossref, Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Arge L, Hoffmann M, Welzl E, eds. Algorithms–ESA 2007, Lecture Notes in Computer Science, vol. 4698 (Springer, Berlin, Heidelberg), 253–264.Google Scholar
• Charikar M, Chekuri C, Pál M (2005) Sampling bounds for stochastic optimization. Chekuri C, Jansen K, Rolim JDP, Trevisan L, eds. Approximation Randomization Combinatorial Optim. Algorithms Techniques, Lecture Notes in Computer Science, vol. 3624 (Springer, Berlin, Heidelberg), 257–269.Google Scholar
• Dasgupta A, Ghosh A, Nazerzadeh H, Raghavan P (2009) Online story scheduling in web advertising. Proc. 20th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1275–1284.Google Scholar
• Deloitte (2021) Covid-19 and shifting generational preferences reshape the future of the US media and entertainment landscape. Accessed August 1, 2021, https://www2.deloitte.com/us/en/pages/about-deloitte/articles/press-releases/digital-media-trends.html.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 (2012) Online matching with concave returns. Proc. 44th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 137–144.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 (Society for Industrial and Applied Mathematics, Philadelphia), 101–107.Google Scholar
• Devanur NR, Jain K, Sivan B, Wilkens CA (2011) Near optimal online algorithms and fast approximation algorithms for resource allocation problems. Proc. 12th ACM Conf. Electronic Commerce (Association for Computing Machinery, New York), 29–38.Google Scholar
• Devanur NR, Huang Z, Korula N, Mirrokni VS, Yan Q (2016) Whole-page optimization and submodular welfare maximization with online bidders. ACM Trans. Econom. Comput. 4(3):1–20.Crossref, Google Scholar
• Dughmi S, Hartline J, Kleinberg RD, Niazadeh R (2021) Bernoulli factories and black-box reductions in mechanism design. J. ACM 68(2):1–30.Crossref, Google Scholar
• Edmonds J (1965) Paths, trees, and flowers. Canadian. J. Math. 17:449–467.Crossref, 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
• Esfandiari H, Korula N, Mirrokni V (2015) Online allocation with traffic spikes: Mixing adversarial and stochastic models. Proc. 16th ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 169–186.Google Scholar
• Feige U (2019) Tighter bounds for online bipartite matching. Bárány I, Katona G, Sali A eds. Building Bridges II, Bolyai Society Mathematical Studies, vol. 28 (Springer, Berlin, Heidelberg), 235–255.Crossref, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009b) Online stochastic matching: Beating 1-1/e. 2009 50th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 117–126.Google Scholar
• Feldman J, Henzinger M, Korula N, Mirrokni VS, Stein C (2010) Online stochastic packing applied to display ad allocation. de Berg M, Meyer U, eds. Algorithms–ESA 2010, Lecture Notes in Computer Science, vol. 6346 (Springer, Berlin, Heidelberg), 182–194.Google Scholar
• Feldman J, Korula N, Mirrokni V, Muthukrishnan S, Pál M (2009a) Online ad assignment with free disposal. Leonardi S, ed. Internet Network Econom. WINE 2009, Lecture Notes in Computer Science, vol. 5929 (Springer, Berlin, Heidelberg), 374–385.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2019) Linear programming based online policies for real-time assortment of reusable resources. Preprint, submitted July 17, http://dx.doi.org/10.2139/ssrn.3421227.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2020) Near-optimal Bayesian online assortment of reusable resources. Chicago Booth Research Paper 20-40, University of Chicago Booth School of Business, Chicago.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2024) Two-stage matching and pricing with applications to ride hailing. Oper. Res. 72(4):1574–1594.Google Scholar
• Feng Y, Niazadeh R, Saberi A (2021) Robustness of online inventory balancing to inventory shocks. Preprint, submitted March 2, http://dx.doi.org/10.2139/ssrn.3795056.Google Scholar
• Frade JLH, Oliveira JHC, Giraldi JME (2021) Advertising in streaming video: An integrative literature review and research agenda. Telecomm. Policy 45(9):102186.Crossref, Google Scholar
• Frank M, Wolfe P (1956) An algorithm for quadratic programming. Naval Res. Logist. Quart. 3(1–2):95–110.Crossref, Google Scholar
• Gallai T (1964) Maximale systeme unabhangiger kanten. Magyar Tud. Akad. Mat. Kutato Int. Kozl. 9:401–413.Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. SODA ‘08: Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms, vol. 8 (Society for Industrial and Applied Mathematics, Philadelphia), 982–991.Google Scholar
• Goel A, Kapralov M, Khanna S (2012) On the communication and streaming complexity of maximum bipartite matching. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 468–485.Google Scholar
• Golrezaei N, Yao E (2021) Online resource allocation with time-flexible customers. Preprint, submitted August 7, https://arxiv.org/abs/2108.03517.Google Scholar
• Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• Gong X-Y, Goyal V, Iyengar GN, Simchi-Levi D, Udwani R, Wang S (2022) Online assortment optimization with reusable resources. Management Sci. 68(7):4772–4785.Link, Google Scholar
• Google YouTube (2021) Personal communication with the YouTube advertising product teams.Google Scholar
• Goyal V, Udwani R (2020) Online matching with stochastic rewards: Optimal competitive ratio via path based formulation. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 791.Google Scholar
• Goyal V, Iyengar G, Udwani R (2020) Online allocation of reusable resources via algorithms guided by fluid approximations. Preprint, submitted October 8, https://arxiv.org/abs/2010.03983.Google Scholar
• Hanasusanto GA, Kuhn D (2018) Conic programming reformulations of two-stage distributionally robust linear programs over Wasserstein balls. Oper. Res. 66(3):849–869.Link, Google Scholar
• Hanasusanto GA, Kuhn D, Wiesemann W (2015) K-adaptability in two-stage robust binary programming. Oper. Res. 63(4):877–891.Link, Google Scholar
• Housni OE, Goyal V, Hanguir O, Stein C (2020) Matching drivers to riders: A two-stage robust approach. Preprint, submitted November 6, https://arxiv.org/abs/2011.03624.Google Scholar
• Huang Z, Zhang Q (2020) Online primal dual meets online matching with stochastic rewards: Configuration LP to the rescue. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1153–1164.Google Scholar
• Huang Z, Kang N, Tang ZG, Wu X, Zhang Y, Zhu X (2018) How to match when all vertices arrive online. Proc. 50th Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 17–29.Google Scholar
• Immorlica N, Karger D, Minkoff M, Mirrokni VS (2004) On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. Proc. 15th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 691–700.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
• Joshi M, Singh A, Ranu S, Bagchi A, Karia P, Kala P (2021) Batching and matching for food delivery in dynamic road networks. 2021 IEEE 37th Internat. Conf. Data Engrg. (ICDE) (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 2099–2104.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. Theoretical Comput. Sci. 408(2–3):213–223.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
• Kuhn D (2006) Generalized Bounds for Convex Multistage Stochastic Programs, vol. 548 (Springer Science & Business Media, Berlin, Heidelberg).Google Scholar
• Lee E, Singla S (2017) Maximum matching in the online batch-arrival model. Eisenbrand F, Koenemann J, eds. Integer Programming Combin. Optim. (IPCO 2017), Lecture Notes in Computer Science, vol. 10328 (Springer, Cham, Switzerland), 355–367.Google Scholar
• Liu T-Y, Ma W, Qin T, Tang P, Yang G, Zheng B (2016) Online non-preemptive story scheduling in web advertising. Proc. 2016 Internat. Conf. Autonomous Agents Multiagent Systems (Singapore), 269–277.Google Scholar
• Lyft (2016) Matchmaking in Lyft line: Part 1. Medium (February 3), https://eng.lyft.com/matchmaking-in-lyft-line-9c2635fe62c4.Google Scholar
• Ma W, Simchi-Levi D (2020) Algorithms for online matching, assortment, and pricing with tight weight-dependent competitive ratios. Oper. Res. 68(6):1787–1803.Link, Google Scholar
• Ma W, Simchi-Levi D, Zhao J (2021) Dynamic pricing (and assortment) under a static calendar. Management Sci. 67(4):2292–2313.Link, Google Scholar
• Manshadi V, Rodilitz S (2020) Online policies for efficient volunteer crowdsourcing. Proc. 21st ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 315–316.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
• Mehta A (2013) Online matching and ad allocation. Foundations Trends Theoretical Comput. Sci. 8(4):265–368.Crossref, Google Scholar
• Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. 2012 IEEE 53rd Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 728–737.Google Scholar
• Mehta A, Waggoner B, Zadimoghaddam M (2014) Online stochastic matching with unequal probabilities. Proc. 26th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1388–1404.Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22–es.Crossref, Google Scholar
• Özkan E, Ward AR (2020) Dynamic matching for real-time ride sharing. Stochastic Systems 10(1):29–70.Link, Google Scholar
• Rogers TN (2019) Amazon’s new waste-reduction strategy: Deliver only once a week. CNN (February 28), https://www.cnn.com/2019/02/28/tech/amazon-day/index.html.Google Scholar
• Rusmevichientong P, Sumida M, Topaloglu H (2020) Dynamic assortment optimization for reusable products with random usage durations. Management Sci. 66(7):2820–2844.Link, Google Scholar
• Shmoys DB, Sozio M (2007) Approximation algorithms for 2-stage stochastic scheduling problems. Fischetti M, Williamson DP, eds. Integer Programming Combin. Optim. IPCO 2007, Lecture Notes in Computer Science, vol. 4513 (Springer, Berlin, Heidelberg), 145–157.Google Scholar
• Shmoys DB, Swamy C (2004) Stochastic optimization is (almost) as easy as deterministic optimization. 45th Annual IEEE Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 228–237.Google Scholar
• Sumita H, Kawase Y, Fujita S, Fukunaga T, Center RA (2017) Online optimization of video ad allocation. Proc. 26th Internat. Joint Conf. Artificial Intelligence (IJCAI, California), 423–429.Google Scholar
• Uber (2020) Uber marketplace and matching. Accessed August 1, 2020, https://marketplace.uber.com/matching.Google Scholar
• Vera A, Banerjee S (2021) The Bayesian prophet: A low-regret framework for online decision making. Management Sci. 67(3):1368–1391.Link, Google Scholar
• Xie Y, Ma W, Xin L (2022) The benefits of delay to online decision-making. Preprint, submitted October 20, http://dx.doi.org/10.2139/ssrn.4248326.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 Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 151–2159.Google Scholar