IEDA Webinar - Submodular Order Functions and Assortment Optimization

10:00am - 11:00am
zoom

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.

Event Format
Speakers / Performers:
Prof. Rajan Udwani
Department of Industrial Engineering and Operations Research, University of California Berkeley

 

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.

 

Language
English
Recommended For
Faculty and staff
PG students
More Information

 

Join Zoom Meeting
https://hkust.zoom.us/j/96640039811?pwd=eDRJQnFYTnF0VmNxaG1zblZ1VUlidz09

Meeting ID: 966 4003 9811
Passcode: 933387

Organizer
Department of Industrial Engineering & Decision Analytics
Department of Information Systems, Business Statistics & Operations Management
Post an event
Campus organizations are invited to add their events to the calendar.