Online Matchings and Beyond: The Power of Water-Filling -
Many modern algorithmic tasks occur in an "online" setting, in which information is revealed sequentially over time, and a decision-maker must make irrevocable decisions as the situation evolves. A classic example is the Online Bipartite Matching problem (OBM). With applications to matching markets, ridesharing platforms, dating apps, and digital advertising, OBM and its variants are very well-studied, and an optimal (1-1/e)-competitive algorithm is known [Karp, Vazirani, Vazirani '90].

In this talk, I will introduce a generalization of OBM called the Online Submodular Assignment problem.  This allows us to capture more complex assignment problems of practical relevance. I will show how "submodular water-levels" can be defined to adapt the water-filling algorithm to the submodular setting, and achieve an optimal (1-1/e)-competitive algorithm for Online SAP as well. 

The talk will be accessible to all undergraduates with familiarity in algorithms, and it is based on joint work with Daniel Hathcock, Billy Jin, Kalen Patton, and Sherry Sarkar.