Maximum Load Assortment Optimization: Approximation Algorithms and Adaptivity Gaps

References

• Adamaszek A, Wiese A (2014) A quasi-PTAS for the two-dimensional geometric knapsack problem. Proc. 26th Ann. ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1491–1505.Google Scholar
• Amorim P, DeHoratius N, Eng-Larsson F, Martins S (2024) Customer preferences for delivery service attributes in attended home delivery. Management Sci. 70(11):7559–7578.Link, Google Scholar
• Aouad A, Segev D (2023) The stability of MNL-based demand under dynamic customer substitution and its algorithmic implications. Oper. Res. 71(4):1216–1249.Link, Google Scholar
• Aouad A, Farias V, Levi R (2021) Assortment optimization under consider-then-choose choice models. Management Sci. 67(6):3368–3386.Link, Google Scholar
• Aouad A, Farias V, Levi R, Segev D (2018) The approximability of assortment optimization under ranking preferences. Oper. Res. 66(6):1661–1669.Link, Google Scholar
• Arora S, Karakostas G (2003) Approximation schemes for minimum latency problems. SIAM J. Comput. 32(5):1317–1337.Crossref, Google Scholar
• Azar Y, Broder AZ, Karlin AR, Upfal E (1994) Balanced allocations. Proc. 26th Ann. ACM Sympos. Theory Comput., 593–602.Google Scholar
• Bai Y, El Housni O, Rusmevichientong P, Topaloglu H (2025) Coordinated inventory stocking and assortment personalization. Oper. Res., ePub ahead of print February 10, https://doi.org/10.1287/opre.2022.0651.Link, Google Scholar
• Bansal N, Chakrabarti A, Epstein A, Schieber B (2006) A quasi-PTAS for unsplittable flow on line graphs. Proc. 38th Ann. ACM Sympos. Theory Comput. (ACM, New York), 721–729.Google Scholar
• Berry PM, Gervasio M, Peintner B, Yorke-Smith N (2007) A preference model for over-constrained meeting requests. Proc. AAAI Workshop Preference Handling Artificial Intelligence (AAAI, Washington, DC), 7–14.Google Scholar
• Blanchet J, Gallego G, Goyal V (2016) A Markov chain approximation to choice modeling. Oper. Res. 64(4):886–905.Link, Google Scholar
• Brzozowski M, Carattini K, Klemmer SR, Mihelich P, Hu J, Ng AY (2006) groupTime: Preference-based group scheduling. Proc. SIGCHI Conf. Human Factors Comput. Systems (ACM, New York), 1047–1056.Google Scholar
• Campbell AM, Savelsbergh M (2006) Incentive schemes for attended home delivery services. Transportation Sci. 40(3):327–341.Link, Google Scholar
• Casazza M, Ceselli A, Létocart L (2016) Optimizing time slot allocation in single operator home delivery problems. Proc. Ann. Internat. Conf. German Oper. Res. Soc. (Springer, New York), 91–97.Google Scholar
• Chan THH, Elbassioni K (2011) A QPTAS for TSP with fat weakly disjoint neighborhoods in doubling metrics. Discrete Comput. Geometry 46:704–723.Crossref, Google Scholar
• Chekuri C, Khanna S (2002) Approximation schemes for preemptive weighted flow time. Proc. 34th Ann. ACM Sympos. Theory Comput. (ACM, New York), 297–305.Google Scholar
• Das A, Mathieu C (2015) A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica 73(1):115–142.Crossref, Google Scholar
• Davis JM, Gallego G, Topaloglu H (2014) Assortment optimization under variants of the nested logit model. Oper. Res. 62(2):250–273.Link, Google Scholar
• Désir A, Goyal V, Jagabathula S, Segev D (2021) Mallows-smoothed distribution over rankings approach for modeling choice. Oper. Res. 69(4):1206–1227.Link, Google Scholar
• El Housni O, Topaloglu H (2023) Joint assortment optimization and customization under a mixture of multinomial logit models: On the value of personalized assortments. Oper. Res. 71(4):1197–1215.Link, Google Scholar
• Farias VF, Jagabathula S, Shah D (2013) A nonparametric approach to modeling choice with limited data. Management Sci. 59(2):305–322.Link, Google Scholar
• Feldman JB, Topaloglu H (2017) Revenue management under the Markov chain choice model. Oper. Res. 65(5):1322–1342.Link, Google Scholar
• Frey J (2009) An algorithm for computing rectangular multinomial probabilities. J. Statist. Comput. Simulations 79(12):1483–1489.Crossref, Google Scholar
• Gallego G, Topaloglu H (2014) Constrained assortment optimization for the nested logit model. Management Sci. 60(10):2583–2601.Link, Google Scholar
• Gallego G, Topaloglu H (2019) Revenue Management and Pricing Analytics (Springer, New York).Crossref, Google Scholar
• Gallego G, Ratliff R, Shebalov S (2015) A general attraction model and sales-based linear program for network revenue management under customer choice. Oper. Res. 63(1):212–232.Link, Google Scholar
• Gao P, Ma Y, Chen N, Gallego G, Li A, Rusmevichientong P, Topaloglu H (2021) Assortment optimization and pricing under the multinomial logit model with impatient customers: Sequential recommendation and selection. Oper. Res. 69(5):1509–1532.Link, Google Scholar
• Hausman J, McFadden D (1984) Specification tests for the multinomial logit model. Econometrica 52(5):1219–1240.Crossref, Google Scholar
• Kök AG, Fisher ML, Vaidyanathan R (2009) Assortment planning: Review of literature and industry practice. Retail Supply Chain Management: Quantitative Models and Empirical Studies (Springer, New York), 99–153.Google Scholar
• Lebrun R (2013) Efficient time/space algorithm to compute rectangular probabilities of multinomial, multivariate hypergeometric and multivariate pólya distributions. Statist. Comput. 23(5):615–623.Crossref, Google Scholar
• Lipton RJ, Markakis E, Mehta A (2003) Playing large games using simple strategies. Proc. 4th ACM Conf. Electronic Commerce (ACM, New York), 36–41.Google Scholar
• Luce RD (1959) Individual Choice Behavior (John Wiley, Hoboken, NJ).Google Scholar
• Mackert J (2019) Choice-based dynamic time slot management in attended home delivery. Comput. Industrial Engrg. 129:333–345.Crossref, Google Scholar
• Mahajan S, Van Ryzin G (2001) Stocking retail assortments under dynamic consumer substitution. Oper. Res. 49(3):334–351.Link, Google Scholar
• Manerba D, Mansini R, Zanotti R (2018) Attended home delivery: Reducing last-mile environmental impact by changing customer habits. IFAC Papers Online 51(5):55–60.Crossref, Google Scholar
• McFadden D (1973) Conditional Logit Analysis of Qualitative Choice Behavior (Institute of Urban and Regional Development, University of California, Berkeley).Google Scholar
• Mirrokni V, Thorup M, Zadimoghaddam M (2018) Consistent hashing with bounded loads. Proc. 29th Ann. ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 587–604.Google Scholar
• Mitzenmacher M, Upfal E (2017) Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Mustafa NH, Raman R, Ray S (2015) Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks and halfspaces. SIAM J. Comput. 44(6):1650–1669.Crossref, Google Scholar
• Phillips RL (2021) Pricing and Revenue Optimization (Stanford University Press, Redwood City, CA).Google Scholar
• Raab M, Steger A (1998) “Balls into bins”: A simple and tight analysis. Proc. Internat. Workshop Randomization Approximation Techniques Comput. Sci. (Springer, New York), 159–170.Google Scholar
• Remy J, Steger A (2009) A quasi-polynomial time approximation scheme for minimum weight triangulation. J. ACM 56(3):1–47.Crossref, Google Scholar
• Rusmevichientong P, Shmoys D, Tong C, Topaloglu H (2014) Assortment optimization under the multinomial logit model with random choice parameters. Production Oper. Management 23(11):2023–2039.Crossref, Google Scholar
• Sumida M, Gallego G, Rusmevichientong P, Topaloglu H, Davis J (2021) Revenue-utility tradeoff in assortment optimization under the multinomial logit model with totally unimodular constraints. Management Sci. 67(5):2845–2869.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
• Truden C, Maier K, Jellen A, Hungerländer P (2022) Computational approaches for grocery home delivery services. Algorithms 15(4):125.Crossref, Google Scholar
• van der Hagen L, Agatz N, Spliet R, Visser TR, Kok L (2024) Machine learning–based feasibility checks for dynamic time slot management. Transportation Sci. 58(1):94–109.Link, Google Scholar
• Waβmuth K, Köhler C, Agatz N, Fleischmann M (2023) Demand management for attended home delivery: A literature review. Eur. J. Oper. Res. 311(3):801–815.Crossref, Google Scholar
• Yang X, Strauss AK (2017) An approximate dynamic programming approach to attended home delivery management. Eur. J. Oper. Res. 263(3):935–945.Crossref, Google Scholar