Near-Optimal Adaptive Policies for Serving Stochastically Departing Customers

References

• Aggarwal G, Goel G, Karande C, Mehta A (2011) Online vertex-weighted bipartite matching and single-bid budgeted allocations. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York, Philadelphia), 1253–1264.Google Scholar
• Akbarpour M, Li S, Gharan SO (2020) Thickness and information in dynamic matching markets. J. Political Econom. 128(3):783–815.Crossref, Google Scholar
• Aksin Z, Armony M, Mehrotra V (2007) The modern call center: A multi-disciplinary perspective on operations management research. Production Oper. Management 16(6):665–688.Crossref, Google Scholar
• Alijani R, Banerjee S, Gollapudi S, Munagala K, Wang K (2020) Predict and match: Prophet inequalities with uncertain supply. Proc. ACM Special Interest Group Measurement Evaluation 04:1–04:23.Google Scholar
• Ancker CJ, Gafarian AV (1963) Some queuing problems with balking and reneging: I. Oper. Res. 11(1):88–100.Link, Google Scholar
• Anderson R, Ashlagi I, Gamarnik D, Kanoria Y (2017) Efficient dynamic barter exchange. Oper. Res. 65(6):1446–1459.Link, Google Scholar
• Aouad A, Saritaç Ö (2022) Dynamic stochastic matching under limited time. Oper. Res. 70(4):2349–2383.Link, Google Scholar
• Aouad A, Segev D (2021) Display optimization for vertically differentiated locations under multinomial logit preferences. Management Sci. 67(6):3519–3550.Link, Google Scholar
• Armony M, Israelit S, Mandelbaum A, Marmor YN, Tseytlin Y, Yom-Tov GB (2015) On patient flow in hospitals: A data-based queueing-science perspective. Stochastic Systems 5(1):146–194.Link, Google Scholar
• Ata B, Tongarlak MH (2013) On scheduling a multiclass queue with abandonments under general delay costs. Queueing Systems 74(1):65–104.Crossref, Google Scholar
• Atar R, Giat C, Shimkin N (2010) The cμ/θ rule for many-server queues with abandonment. Oper. Res. 58(5):1427–1439.Link, Google Scholar
• Baras JS, Dorsey AJ, Makowski AM (1985) Two competing queues with linear costs and geometric service requirements: The μc-rule is often optimal. Adv. Appl. Probability 17(1):186–209.Crossref, Google Scholar
• Batt RJ, Terwiesch C (2015) Waiting patiently: An empirical study of queue abandonment in an emergency department. Management Sci. 61(1):39–59.Link, Google Scholar
• Brubach B, Grammel N, Ma W, Srinivasan A (2024) Online matching frameworks under stochastic rewards, product ranking, and unknown patience. Oper. Res., ePub ahead of print October 27, https://doi.org/10.1287/opre.2021.0371.Google Scholar
• Buyukkoc C, Varaiya P, Walrand J (1985) The cμ rule revisited. Adv. Appl. Probability 17(1):237–238.Crossref, Google Scholar
• Cadas A, Bušić A, Doncel J (2019) Optimal control of dynamic bipartite matching models. Proc. 12th EAI Internat. Conf. Performance Evaluation Methodologies Tools (Association for Computing Machinery, New York), 39–46.Google Scholar
• Collina N, Immorlica N, Leyton-Brown K, Lucier B, Newman N (2020) Dynamic weighted matching with heterogeneous arrival and departure rates. Chen X, Gravin N, Hoefer M, Mehta R, eds. Proc. 16th Internat. Conf. Web Internet Econom. (Springer Nature, Berlin, Switzerland), 17–30.Google Scholar
• Cygan M, Englert M, Gupta A, Mucha M, Sankowski P (2013) Catch them if you can: How to serve impatient users. Kleinberg RD, ed. Proc. 4th Innovations Theoretical Comput. Sci. Conf. (Association for Computing Machinery, New York), 485–494.Google Scholar
• Derakhshan M, Golrezaei N, Manshadi VH, Mirrokni V (2022) Product ranking on online platforms. Management Sci. 68(6):4024–4041.Link, Google Scholar
• Feldman JB, Segev D (2022) Technical note: The multinomial logit model with sequential offerings: Algorithmic frameworks for product recommendation displays. Oper. Res. 70(4):2162–2184.Link, Google Scholar
• Gallego G, Li A, Truong V, Wang X (2020) Approximation algorithms for product framing and pricing. Oper. Res. 68(1):134–160.Link, Google Scholar
• Garnett O, Mandelbaum A, Reiman M (2002) Designing a call center with impatient customers. Manufacturing Service Oper. Management 4(3):208–227.Link, Google Scholar
• Gupta A (2016) Approximation algorithms for optimization under uncertainty. Proc. Uncertainty Comput. Workshop.Google Scholar
• Haight F (1959) Queueing with reneging. Metrika 2(1):186–197.Crossref, Google Scholar
• Harris CM, Hoffman KL, Saunders PB (1987) Modeling the IRS telephone taxpayer information system. Oper. Res. 35(4):504–523.Link, Google Scholar
• Jez L (2011) One to rule them all: A general randomized algorithm for buffer management with bounded delay. Demetrescu C, Halldórsson MM, eds. Proc. 19th Annual Eur. Sympos. Algorithms (Springer Nature, Berlin, Switzerland), 239–250.Google Scholar
• Kessel K, Shameli A, Saberi A, Wajc D (2022) The stationary prophet inequality problem. Pennock DM, Segal I, Seuken S, eds. Proc. 23rd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 243–244.Google Scholar
• Klimov GP (1975) Time-sharing service systems: I. Theory Probability Appl. 19(3):532–551.Crossref, Google Scholar
• MacRury C, Ma W, Grammel N (2023) On (random-order) online contention resolution schemes for the matching polytope of (bipartite) graphs. Bansal N, Nagarajan V, eds. Proc. 34th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM-SIAM, New York, Philadelphia), 1995–2014.Google Scholar
• Özkan E, Ward AR (2020) Dynamic matching for real-time ride sharing. Stochastic Systems 10(1):29–70.Link, Google Scholar
• Papadimitriou C, Pollner T, Saberi A, Wajc D (2024) Online stochastic max-weight bipartite matching: Beyond prophet inequalities. Math. Oper. Res. 49(3):1607–1628.Link, Google Scholar
• Tsitsiklis JN, Xu K (2017) Flexible queueing architectures. Oper. Res. 65(5):1398–1413.Link, Google Scholar
• Van Mieghem JA (1995) Dynamic scheduling with convex delay costs: The generalized cμ rule. Ann. Appl. Probability 5(3):809–833.Crossref, Google Scholar
• Wang K, Li N, Jiang Z (2010) Queueing system with impatient customers: A review. Proc. IEEE Internat. Conf. Service Oper. Logist. Informatics (IEEE, Piscataway, NJ), 82–87.Google Scholar
• Yan C, Zhu H, Korolko N, Woodard D (2020) Dynamic pricing and matching in ride-hailing platforms. Naval Res. Logist. 67(8):705–724.Crossref, Google Scholar
• Zeltyn S, Mandelbaum A (2005) Call centers with impatient customers: Many-server asymptotics of the M/M/n+G queue. Queueing Systems 51(3):361–402.Crossref, Google Scholar