TITLE:   Multi-stage and Multi-customer Assortment Optimization with Inventory Constraints

ABSTRACT

We consider an assortment optimization problem where a customer chooses a single item from a sequence of sets shown to her, while limited inventories constrain the items offered to customers over time. In the special case where all of the assortments have size one, our problem captures the online stochastic matching with timeouts problem. For this problem, we derive a polynomial-time approximation algorithm which earns at least 1-ln(2-1/e), or 0.51, of the optimum. This improves upon the previous-best approximation ratio of 0.46, and furthermore, we show that it is tight. For the general assortment problem, we establish the first constant-factor approximation ratio of 0.09 for the problem. Our algorithms are based on rounding an LP relaxation for multi-stage assortment optimization, and improve upon previous randomized rounding schemes to derive the tight ratio of 1-ln(2-1/e).

BIO SKETCH

Elaheh Fata is a PhD candidate at the Massachusetts Institute of Technology working with Prof. David Simchi-Levi and Prof. Georgia Perakis. Her current research interests are in the areas of optimization algorithms and machine learning with applications to revenue management, pricing, and online marketplaces. Previously, she has conducted research in the areas of vehicle routing, multi-agent systems, graph-theoretic analysis of large-scale systems, and game theory. Prior to joining MIT, Elaheh received a MASc degree from the University of Waterloo and a BSc degree from Sharif University.