排名(信息检索)
近似硬度
数学优化
简单(哲学)
计算机科学
组合优化
任务(项目管理)
最优化问题
收入
近似算法
数学
人工智能
经济
会计
认识论
哲学
管理
作者
Ali Aouad,Vivek F. Farias,Retsef Levi,Danny Segev
出处
期刊:Operations Research
[Institute for Operations Research and the Management Sciences]
日期:2018-11-01
卷期号:66 (6): 1661-1669
被引量:68
标识
DOI:10.1287/opre.2018.1754
摘要
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.
科研通智能强力驱动
Strongly Powered by AbleSci AI