The Approximability of Assortment Optimization Under Ranking Preferences
研究了在消费者偏好由排名分布表示的通用模型下，品类优化问题的最佳近似界限，揭示了该问题与图论中最大独立集检测的联系，并给出了紧的近似算法。
Assortment optimization has received significant attention in recent revenue management and combinatorial optimization literature. In “The Approximability of Assortment Optimization Under Ranking Preferences,” A. Aouad, V. Farias, R. Levi, and D. Segev provide best-possible approximability bounds for this problem under an almost general model specification, where preferences are expressed as a distribution over rankings. This paper shows how this optimization problem relates to the computational task of detecting large independent sets in graphs, allowing the establishment of strong complexity lower bounds with respect to various problem parameters. These findings are complemented by a number of algorithms that attain essentially best-possible approximation factors, proving that the hardness results are tight up to lower-order terms. Surprisingly, their results imply that a simple and widely studied policy, known as revenue-ordered assortments, achieves the best possible performance guarantee with respect to prices.