The approximability of assortment optimization under ranking preferences

Aouad, A, Farias, V, Levi, R and Segev, D (2018) The approximability of assortment optimization under ranking preferences. Operations Research, 66 (6). pp. 1661-1669. ISSN 0030-364X OPEN ACCESS

Abstract

The main contribution of this paper is to provide best-possible approximability bounds for assortment planning under a general choice model, where customer choices are modeled through an arbitrary distribution over ranked lists of their preferred products, subsuming most random utility choice models of interest. From a technical perspective, we show how to relate this optimization problem to the computational task of detecting large independent sets in graphs, allowing us to argue that general ranking preferences are extremely hard to approximate with respect to various problem parameters. These findings are complemented by a number of approximation algorithms that attain essentially best-possible factors, proving that our hardness results are tight up to lower-order terms. Surprisingly, our results imply that a simple and widely studied policy, known as revenue-ordered assortments, achieves the best possible performance guarantee with respect to the price parameters.

More Details

Item Type: Article
Subject Areas: Management Science and Operations
Subjects: C > Choice
A > Algorithms
A > Approximations
Date Deposited: 19 Feb 2019 09:22
Last Modified: 21 Sep 2019 13:39
URI: http://lbsresearch.london.edu/id/eprint/1085
More

Export and Share


Download

Accepted Version - Text

Statistics

Altmetrics
View details on Dimensions' website

Downloads from LBS Research Online

View details

Actions (login required)

Edit Item Edit Item