Maximum Load Assortment Optimization: Approximation Algorithms and Adaptivity Gaps.

This article introduces and studies a novel class of assortment optimization problems called maximum load assortment optimization (MLA), motivated by applications such as attended home delivery and preference-based group scheduling. Under the multinomial logit (MNL) choice model, the objective is to offer product assortments to a stream of customers to maximize the expected maximum load—that is, the highest number of customers selecting the same product—considering both static (same assortment for all customers) and dynamic (personalized assortments) settings. The authors develop a polynomial time evaluation oracle for the static problem, prove the existence of a preference weight–ordered assortment yielding a 1/2 approximation, and present a polynomial time approximation scheme (PTAS). For the dynamic setting, they establish a constant adaptivity gap bounded by four, provide a 1/4 approximation via static policies, and design a quasi-polynomial time adaptive policy achieving a (1−ϵ)-approximation. Numerical experiments reveal that optimal static assortments tend to shrink as the number of customers or preference weights increase. The paper concludes with open questions on computational complexity, improved adaptivity gap bounds, practical applications, and extensions to other choice models and constraints.