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 guarantees 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.

Papers related to the talk:
https://arxiv.org/pdf/2107.02743.pdf

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.

For more information about the ESD Seminar, please email esd_invite@sutd.edu.sg