Prophet Inequalities for a New Class of Overbooking Problems in Container Shipping

References

• Arnosti N, Ma W (2023) Tight guarantees for static threshold policies in the prophet secretary problem. Oper. Res. 71(5):1777–1788.Link, Google Scholar
• Böckenhauer HJ, Klasing R, Mömke T, Rossmanith P, Stocker M, Wehner D (2023) Online knapsack with removal and recourse. Hsieh SY, Hung LJ, Lee CW, eds. Combinatorial Algorithms: 34th International Workshop, IWOCA 2023, Proceedings. Lecture Notes in Computer Science, vol. 13889 (Springer, Cham, Switzerland), 123–135.Google Scholar
• Brooks C (2016) Reducing canceled freight booking avenue for liner, shipper cooperation. J. Commerce (October 23), https://www.joc.com/article/reducing-canceled-freight-booking-avenue-for-liner-shipper-cooperation-5683330.Google Scholar
• Correa J, Foncea P, Hoeksma R, Oosterwijk T, Vredeveld T (2019) Recent developments in prophet inequalities. ACM SIGecom Exchanges 17(1):61–70.Crossref, Google Scholar
• Ekbatani F, Feng Y, Niazadeh R (2022) Online resource allocation with buyback: Optimal algorithms via primal-dual. Preprint, submitted October 20, https://arxiv.org/abs/2210.11570v1.Google Scholar
• Elmaghraby W, Lippman SA, Tang CS, Yin R (2009) Will more purchasing options benefit customers? Production Oper. Management 18(4):381–401.Crossref, Google Scholar
• Epstein B, Ma W (2024) Selection and ordering policies for hiring pipelines via linear programming. Oper. Res. 72(5):2000–2013.Link, Google Scholar
• Ezra T, Feldman M, Nehama I (2018) Prophets and secretaries with overbooking. Tardos É, Elkind E, Vohra R, eds. Proc. 2018 ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 319–320.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
• Freund D, Zhao J (2021) Overbooking with bounded loss. Biró P, Chawla S, Echenique F, eds. Proc. 22nd ACM Conf. Econom. Comput. (Association for Computing Machinery, New York), 477–478.Google Scholar
• Gallego G, Şahin Ö (2010) Revenue management with partially refundable fares. Oper. Res. 58(4-part-1):817–833.Link, Google Scholar
• Gallego G, Topaloglu H (2019) Overbooking. Revenue Management and Pricing Analytics (Springer, New York), 83–105.Crossref, Google Scholar
• Gan RJ, Gans N, Tsoukalas G (2019) Overbooking with endogenous demand. Working paper, The Wharton School, University of Pennsylvania, Philadelphia.Google Scholar
• Georgiadis G, Tang CS (2014) Optimal reservation policies and market segmentation. Internat. J. Production Econom. 154:81–99.Crossref, Google Scholar
• Han X, Kawase Y, Makino K (2014) Online unweighted knapsack problem with removal cost. Algorithmica 70(1):76–91.Crossref, Google Scholar
• Hill TP, Kertz RP (1992) A survey of prophet inequalities in optimal stopping theory. Contemporary Math. 125(1):191–207.Crossref, Google Scholar
• Iwama K, Taketomi S (2002) Removable online knapsack problems. Widmayer P, Triguero F, Morales R, Hennessy M, Eidenbenz S, Conejo R, eds. Automata, Languages and Programming: 29th Internat.Colloquium, ICALP 2002, Proceedings. Lecture Notes in Computer Science, vol. 2380 (Springer, Berlin, Heidelberg), 293–305.Google Scholar
• JOC Staff (2020) NYSHEX volume tripled, membership doubled in 2019. J. Commerce (January 29), https://www.joc.com/article/nyshex-volume-tripled-membership-doubled-in-2019-5206615.Google Scholar
• Karaesmen I, Van Ryzin G (2004) Overbooking with substitutable inventory classes. Oper. Res. 52(1):83–104.Link, Google Scholar
• Krengel U, Sucheston L (1977) Semiamarts and finite values. Bull. Amer. Math. Soc. 83(4):745–747.Crossref, Google Scholar
• Morley HR (2017a) Cargo-booking exchange aims to give BCOs certainty. J. Commerce (March 2), https://www.joc.com/maritime-news/container-lines/cargo-booking-exchange-aims-give-bcos-certainty_20170302.html. Google Scholar
• Morley HR (2017b) New ways to reduce container booking no-shows emerge. J. Commerce (July 27), https://www.joc.com/technology/new-ways-reduce-container-booking-no-shows-come-focus_20170727.html.Google Scholar
• Noone BM, Lee CH (2011) Hotel overbooking: The effect of overcompensation on customers’ reactions to denied service. J. Hospitality Tourism Res. 35(3):334–357.Crossref, Google Scholar
• Oh J, Su X (2022) Optimal pricing and overbooking of reservations. Production Oper. Management 31(3):928–940.Crossref, Google Scholar
• Osadchiy N, Vulcano G (2010) Selling with binding reservations in the presence of strategic consumers. Management Sci. 56(12):2173–2190.Link, Google Scholar
• Perez-Salazar S, Singh M, Toriello A (2021) Robust online selection with uncertain offer acceptance. Preprint, submitted December 1, https://arxiv.org/abs/2112.00842v1.Google Scholar
• Perez-Salazar S, Singh M, Toriello A (2022) The IID prophet inequality with limited flexibility. Preprint, submitted October 11, https://arxiv.org/abs/2210.05634v1.Google Scholar
• Popescu A, Keskinocak P, Johnson E, LaDue M, Kasilingam R (2006) Estimating air-cargo overbooking based on a discrete show-up-rate distribution. Interfaces 36(3):248–258.Link, Google Scholar
• Rothstein M (1971) An airline overbooking model. Transportation Sci. 5(2):180–192.Link, Google Scholar
• Rothstein M (1974) Hotel overbooking as a Markovian sequential decision process. Decision Sci. 5(3):389–404.Crossref, Google Scholar
• Samuel-Cahn E (1984) Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12(4):1213–1216.Crossref, Google Scholar
• Sierag DD, Koole G, van der Mei RD, Van der Rest J, Zwart B (2015) Revenue management under customer choice behaviour with cancellations and overbooking. Eur. J. Oper. Res. 246(1):170–185.Crossref, Google Scholar
• Smith BC, Leimkuhler JF, Darrow RM (1992) Yield management at American Airlines. Interfaces 22(1):8–31.Link, Google Scholar
• Solomon M (2018) Can IT help the shipping industry deep-six the container “no-show” problem? DC Velocity (March 29), https://www.dcvelocity.com/articles/29615-can-it-help-the-shipping-industry-deep-six-the-container-no-show-problem.Google Scholar
• Sumida M, Topaloglu H (2019) An approximation algorithm for capacity allocation over a single flight leg with fare-locking. INFORMS J. Comput. 31(1):83–99.Link, Google Scholar
• Thompson H (1961) Statistical problems in airline reservation control. Oper. Res. Quart. 12(3):167–185.Crossref, Google Scholar
• Topaloglu H, Birbil SI, Frenk J, Noyan N (2012) Tractable open loop policies for joint overbooking and capacity control over a single flight leg with multiple fare classes. Transportation Sci. 46(4):460–481.Link, Google Scholar
• Yao ACC (1977) Probabilistic computations: Toward a unified measure of complexity. 18th Annual Sympos. Foundations Comput. Sci. (SFCS 1977) (IEEE, Piscataway, NJ), 222–227.Google Scholar
• Zacharias C, Pinedo M (2014) Appointment scheduling with no-shows and overbooking. Production Oper. Management 23(5):788–801.Crossref, Google Scholar
• Zhao H, Meng Q, Wang Y (2020) Probability estimation model for the cancellation of container slot booking in long-haul transports of intercontinental liner shipping services. Transportation Res. Part C Emerging Tech. 119:102731.Crossref, Google Scholar
• Zhou Y, Chakrabarty D, Lukose R (2008) Budget constrained bidding in keyword auctions and online knapsack problems. Papadimitriou C, Zhang S, eds. Internet and Network Economics: 4th International Workshop, Proceedings. Lecture Notes in Computer Science, vol. 5385 (Springer, Berlin, Heidelberg), 566–576.Google Scholar