IEDA Webinar - Submodular Order Functions and Assortment Optimization

We define a new class of set functions that in addition to being monotone and subadditive, also admit a very limited form of submodularity defined over a permutation of the ground set. We refer to this permutation as a submodular order. We give fast and best possible approximation algorithms for constrained maximization of submodular order functions. Applying this new notion to the problem of assortment optimization, we obtain new and in some cases the first constant factor guarantee for constrained assortment optimization in fundamental choice models. We also show an intriguing connection to the maximization of monotone submodular functions in the streaming model, where we recover best known approximation guarantees as a corollary of our results.