Abstract: 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.
Bio: Rajan Udwani is an Assistant Professor of Industrial Engineering and Operations Research at UC Berkeley. Prior to joining UC Berkeley he was a postdoctoral researcher at Columbia University. He holds a B.Tech in Electrical Engineering from IIT Bombay and a PhD in Operations Research from MIT. He works on algorithms for optimization under uncertainty with a focus on revenue management and pricing. His work has been recognized by INFORMS junior faculty and student paper awards.
