Prof. Rajan Udwani Wins INFORMS Junior Faculty Interest Group Paper Competition
Berkeley IEOR Professor Rajan Udwani has been selected as winner of the 2021 INFORMS Junior Faculty Interest Group (JFIG) Paper Competition for his work titled Submodular Order Functions and Assortment Optimization.
Udwani was selected for his work with submodular order functions and demonstrating the power of submodular order functions.
As part of the paper competition, all selected finalists presented their work at the INFORMS Annual Conference. Among all finalists, Professor Udwani was awarded first place. Berkeley IEOR extends a hearty congratulations to the researchers for the award!
The abstract to the paper is provided below. To access to paper, click here.
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. This class of functions includes monotone submodular functions as a sub-family. To understand the importance of this structure in optimization problems we consider the problem of maximizing function value under various types of constraints.
To demonstrate the modeling power of submodular order functions we show applications in two different settings. First, we apply our results to the extensively studied problem of assortment optimization. While the objectives in assortment optimization are known to be non-submodular (and non-monotone) even for simple choice models, we show that they are compatible with the notion of submodular order. Consequently, we obtain new and in some cases the first constant factor guarantee for constrained assortment optimization in fundamental choice models. As a second application of submodular order functions, we show an intriguing connection to the maximization of monotone submodular functions in the streaming model. We recover some best known guarantees for this problem as a corollary of our results.
