Technical Note—Capacitated Assortment Optimization: Hardness and Approximation
研究了容量约束下的品类优化问题，证明即使对简单多项Logit模型也是NP难的，并针对混合多项Logit、马尔可夫链等模型给出了近似最优算法。
Assortment optimization is an important problem arising in various applications. In many practical settings, the assortment is subject to a capacity constraint. In “Capacitated Assortment Optimization: Hardness and Approximation,” Désir, Goyal, and Zhang study the capacitated assortment optimization problem. The authors first show that adding a general capacity constraint makes the problem NP-hard even for the simple multinomial logit model. They also show that under the mixture of multinomial logit model, even the unconstrained problem is hard to approximate within any reasonable factor when the number of mixtures is not constant. In view of these hardness results, the authors present near-optimal algorithms for a large class of parametric choice models including the mixture of multinomial logit, Markov chain, nested logit, and d-level nested logit choice models. In fact, their approach extends to a large class of objective functions that depend only on a small number of linear functions.