Relating the Approximability of the Fixed Cost and Space Constrained Assortment Problems

Abstract

We study the classic assortment optimization problem in which a retailer seeks the revenue maximizing set of products to offer to each arriving customer. This study relates two variants of this assortment problem: the space constrained assortment problem, in which the retailer has a limit on the total space of the offered assortment, and the fixed cost assortment problem, in which the retailer incurs a fixed cost for each offered product. In particular, we develop an approximation scheme for the space constrained problem for any random utility choice model that only relies on the ability to solve the corresponding fixed cost assortment problem. We then apply this technique to give a constant factor approximation scheme for the space constrained assortment problem under a classical model for vertically differentiated products. Last, we present computational results to show the efficacy of this approach.