Advance Service Reservations with Heterogeneous Customers

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
• Agrawal S, Wang Z, Ye Y (2014) A dynamic near-optimal algorithm for online linear programming. Oper. Res. 62(4):876–890.Google Scholar
• Alaei S, Hajiaghayi MT, Liaghat V, Pei D, Saha B (2011) Adcell: Ad allocation in cellular networks. Demetrescu C, Halldórsson MM, eds. Algorithms – ESA 2011 (Springer, Berlin, Heidelberg), 311–322.Google Scholar
• Allen-Zhu Z, Orecchia L (2019) Nearly linear-time packing and covering LP solvers. Math. Programming 175(1):307–353.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
• Bhalgat A, Feldman J, Mirrokni V (2012) Online allocation of display ads with smooth delivery. Proc. 18th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1213–1221.Google Scholar
• Borodin A, El-Yaniv R (2005) Online Computation and Competitive Analysis (Cambridge University Press).Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. Algorithms – ESA 2007 (Springer, Berlin, Heidelberg), 253–264.Google Scholar
• Chen K, Ross SM (2014) An adaptive stochastic knapsack problem. Eur. J. Oper. Res. 239(3):625–635.Crossref, Google Scholar
• Ciocan DF, Farias VF (2012) Dynamic allocation problems with volatile demand. Math. Oper. Res. 37(3):501–525.Link, 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 (ACM, 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
• Devanur NR, Sivan B, Azar Y (2012) Asymptotically optimal algorithm for stochastic adwords. Proc. 13th ACM Conf. Electronic Commerce (ACM, New York), 388–404.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 (ACM, New York), 29–38.Google Scholar
• Feldman J, Liu N, Topaloglu H, Ziya S (2014) Appointment scheduling under patient preference and no-show behavior. Oper. Res. 62(4):794–811.Link, Google Scholar
• Feldman J, Mehta A, Mirrokni V, Muthukrishnan S (2009) Online stochastic matching: Beating 1-1/e. Foundations of Comput. Sci., 2009. FOCS’09. 50th Annual IEEE Sympos. (IEEE, Washington, DC), 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 (Springer, Berlin, Heidelberg), 182–194.Google Scholar
• Gallego G, Li A, Truong V-A, Wang X (2015) Online resource allocation with customer choice. Working paper, Columbia University, New York.Google Scholar
• Ghosh A, McAfee P, Papineni K, Vassilvitskii S (2009) Bidding for representative allocations for display advertising. Leonardi S, ed. Internet and Network Economics (Springer, Berlin, Heidelberg), 208–219.Google Scholar
• Gocgun Y, Ghate A (2012) Lagrangian relaxation and constraint generation for allocation and advanced scheduling. Comput. Oper. Res. 39(10):2323–2336.Crossref, Google Scholar
• Goel G, Mehta A (2008) Online budgeted matching in random input models with applications to adwords. Proc. 19th Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 982–991.Google Scholar
• Gupta D, Wang L (2008) Revenue management for a primary-care clinic in the presence of patient choice. Oper. Res. 56(3):576–592.Link, Google Scholar
• Huh T, Liu N, Truong V (2012) Multi-resource allocation scheduling in dynamic environments. Manufacturing Service Oper. Management 15(2):280–291.Link, Google Scholar
• Jaillet P, Lu X (2011) Online resource allocation problems. Working paper, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Jaillet P, Lu X (2012) Near-optimal online algorithms for dynamic resource allocation problems. Working paper, Massachusetts Institute of Technology, Cambridge.Google Scholar
• Jaillet P, Lu X (2013) Online stochastic matching: New algorithms with better bounds. Math. Oper. Res. 39(3):624–646.Link, Google Scholar
• Kalyanasundaram B, Pruhs K (1996) An optimal deterministic algorithm for online b-matching. Chandru V, Vinay V, eds. Foundations of Software Technology and Theoretical Computer Science (Springer-Verlag, Berlin, Heidelberg), 193–199.Google Scholar
• Karande C, Mehta A, Tripathi P (2011) Online bipartite matching with unknown distributions. Proc. 43rd Annual ACM Sympos. Theory Comput. (ACM, 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. STOC ’90 (ACM, New York), 352–358.Crossref, Google Scholar
• Kim S-H, Whitt W (2014) Are call center and hospital arrivals well modeled by nonhomogeneous Poisson processes? Manufacturing Service Oper. Management 16(3):464–480.Link, Google Scholar
• Kleywegt AJ, Papastavrou JD (1998) The dynamic and stochastic knapsack problem. Oper. Res. 46(1):17–35.Link, Google Scholar
• Lin GY, Lu Y, Yao DD (2008) The stochastic knapsack revisited: Switch-over policies and dynamic pricing. Oper. Res. 56(4):945–957.Link, Google Scholar
• Lueker GS (1998) Average-case analysis of off-line and on-line knapsack problems. J. Algorithms 29(2):277–305.Crossref, Google Scholar
• Mahdian M, Yan Q (2011) Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. Proc. 43rd Annual ACM Sympos. Theory Comput. (ACM, New York), 597–606.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
• Marchetti-Spaccamela A, Vercellis C (1995) Stochastic on-line knapsack problems. Math. Programming 68(1–3):73–104.Crossref, Google Scholar
• Mehta A (2012) Online matching and ad allocation. Theoretical Comput. Sci. 8(4):265–368.Google Scholar
• Mehta A, Saberi A, Vazirani U, Vazirani V (2007) Adwords and generalized online matching. J. ACM 54(5):22.Crossref, Google Scholar
• Mirrokni VS, Gharan SO, Zadimoghaddam M (2012) Simultaneous approximations for adversarial and stochastic online budgeted allocation. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1690–1701.Google Scholar
• Papastavrou JD, Rajagopalan S, Kleywegt AJ (1996) The dynamic and stochastic knapsack problem with deadlines. Management Sci. 42(12):1706–1718.Link, Google Scholar
• Patrick J, Puterman ML, Queyranne M (2008) Dynamic multi-priority patient scheduling for a diagnostic resource. Oper. Res. 56(6):1507–1525.Link, Google Scholar
• Spivey MZ, Powell WB (2004) The dynamic assignment problem. Transportation Sci. 38(4):399–419.Link, Google Scholar
• Truong VA (2015) Optimal advance scheduling. Management Sci. 61(7):1584–1597.Link, Google Scholar
• Van Slyke R, Young Y (2000) Finite horizon stochastic knapsacks with applications to yield management. Oper. Res. 48(1):155–172.Link, Google Scholar
• Vee E, Vassilvitskii S, Shanmugasundaram J (2010) Optimal online assignment with forecasts. Proc. 11th ACM Conf. Electronic Commerce (ACM, New York), 109–118.Google Scholar
• Wang X, Truong V, Bank D (2018) Online advance admission scheduling for services, with customer preferences. Working paper, submitted May 26, https://arxiv.org/abs/1805.10412.Google Scholar
• Zhou Y, Chakrabarty D, Lukose R (2008) Budget constrained bidding in keyword auctions and online knapsack problems. Papadimitriou C, Zhang S, eds. Proc. 4th Workshop Internet and Network Economics (Springer, Berlin, Heidelberg), 566–576.Google Scholar