Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios

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 Symp. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1253–1264.Google Scholar
• Araman VF, Caldentey R (2011) Revenue management with incomplete demand information. Cochran JJ, Cox LA Jr, Keskinocak P, Kharoufeh JP, Smith JC, eds. Wiley Encyclopedia Operations Research and Management Science (John Wiley & Sons, Hoboken, NJ), 1–17.Crossref, Google Scholar
• Badanidiyuru A, Kleinberg R, Slivkins A (2013) Bandits with knapsacks. Proc. IEEE 54th Annual Symp. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, New York), 207–216.Google Scholar
• Ball MO, Queyranne M (2009) Toward robust revenue management: Competitive analysis of online booking. Oper. Res. 57(4):950–963.Link, Google Scholar
• Bodea T, Ferguson M, Garrow L (2009) Data set—Choice-based revenue management: Data from a major hotel chain. Manufacturing Service Oper. Management 11(2):356–361.Link, Google Scholar
• Borodin A, El-Yaniv R (2005) Online Computation and Competitive Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Buchbinder N, Jain K, Naor JS (2007) Online primal-dual algorithms for maximizing ad-auctions revenue. European Symp. Algorithms (Springer), 253–264.Google Scholar
• Chan CW, Farias VF (2009) Stochastic depletion problems: Effective myopic policies for a class of dynamic optimization problems. Math. Oper. Res. 34(2):333–350.Link, Google Scholar
• Chen X, Ma W, Simchi-Levi D, Xin L (2016) Dynamic recommendation at checkout under inventory constraint. Working paper, Columbia University, New York.Google Scholar
• Chen Y, Farias VF (2013) Simple policies for dynamic pricing with imperfect forecasts. Oper. Res. 61(3):612–624.Link, Google Scholar
• Cheung WC, Simchi-Levi D (2016) Efficiency and performance guarantees for choice-based network revenue management problems with flexible products. Working paper, National University of Singapore.Google Scholar
• Ciocan DF, Farias V (2012) Model predictive control for dynamic resource allocation. Math. Oper. Res. 37(3):501–525.Link, Google Scholar
• Devanur NR, Jain K (2012) Online matching with concave returns. Proc. 44th Annual ACM Symp. 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 Symp. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 101–107.Google Scholar
• Feldman J, Henzinger M, Korula N, Mirrokni V, Stein C (2010) Online stochastic packing applied to display ad allocation. Proc. 18th Annual Eur. Conf. Algorithms: Part II: Algorithms–ESA (Springer, Berlin), 182–194.Google Scholar
• Feldman J, Korula N, Mirrokni V, Muthukrishnan S, Pál M (2009) Online ad assignment with free disposal. Proc. Internat. Workshop Internet Network Econom. (Springer, Berlin), 374–385.Google Scholar
• Ferreira KJ, Simchi-Levi D, Wang H (2018) Online network revenue management using Thompson sampling. Oper. Res. 66(6):1586–1602.Google Scholar
• Golrezaei N, Nazerzadeh H, Rusmevichientong P (2014) Real-time optimization of personalized assortments. Management Sci. 60(6):1532–1551.Link, Google Scholar
• Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Math. Oper. Res. 37(2):313–345.Link, Google Scholar
• Karp RM, Vazirani UV, Vazirani VV (1990) An optimal algorithm for on-line bipartite matching. Proc. 22nd Annual ACM Symp. Theory Comput. (Association for Computing Machinery, New York), 352–358.Google Scholar
• Kesselheim T, Radke K, Tönnis A, Vöcking B (2013) An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. Eur. Symp. Algorithms (Springer, Berlin), 589–600.Google Scholar
• Lan Y, Gao H, Ball MO, Karaesmen I (2008) Revenue management with limited demand information. Management Sci. 54(9):1594–1609.Link, Google Scholar
• Liu Q, Van Ryzin G (2008) On the choice-based linear programming model for network revenue management. Manufacturing Service Oper. Management 10(2):288–310.Link, Google Scholar
• Ma W, Simchi-Levi D (2019) Tight weight-dependent competitive ratios for online edge-weighted bipartite matching and beyond. Proc. ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 727–728.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 Theoret. Comput. Sci. 8(4):265–368.Google Scholar
• Mehta A, Panigrahi D (2012) Online matching with stochastic rewards. Proc. IEEE 53rd Annual Symp. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, New York), 728–737.Google Scholar
• Mehta A, Waggoner B, Zadimoghaddam M (2014) Online stochastic matching with unequal probabilities. Proc. 26th Annual ACM-SIAM Symp. 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:1–22:19.Crossref, Google Scholar
• Newman JP, Ferguson ME, Garrow LA, Jacobs TL (2014) Estimation of choice-based models using sales data from a single firm. Manufacturing Service Oper. Management 16(2):184–197.Link, Google Scholar
• Reiman MI, Wang Q (2008) An asymptotically optimal policy for a quantity-based network revenue management problem. Math. Oper. Res. 33(2):257–282.Link, Google Scholar
• Talluri K, Van Ryzin G (2004) Revenue management under a general discrete choice model of consumer behavior. Management Sci. 50(1):15–33.Link, Google Scholar
• Talluri KT, Van Ryzin GJ (2006) The Theory and Practice of Revenue Management, vol. 68 (Springer Science & Business Media, Berlin).Google Scholar
• Van Ryzin G, McGill J (2000) Revenue management without forecasting or optimization: An adaptive algorithm for determining airline seat protection levels. Management Sci. 46(6):760–775.Link, Google Scholar
• van Ryzin G, Vulcano G (2014) A market discovery algorithm to estimate a general class of nonparametric choice models. Management Sci. 61(2):281–300.Link, Google Scholar
• Wang X, Truong V, Bank D (2015) Online advance admission scheduling for services, with customer preferences. Working paper, Columbia University, New York.Google Scholar
• Yao ACC (1977) Probabilistic computations: Toward a unified measure of complexity. Proc.18th Annual Symp. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, New York), 222–227.Google Scholar
• Zhang D, Cooper WL (2005) Revenue management for parallel flights with customer-choice behavior. Oper. Res. 53(3):415–431.Link, Google Scholar
• Zhang H, Shi C, Qin C, Hua C (2016) Stochastic regret minimization for revenue management problems with nonstationary demands. Naval Res. Logist. 63(6):433–448.Crossref, Google Scholar