Recent Progress on Submodular Function Minimization
6Haotian Jiang (Microsoft Research, Redmond)
https://simons.berkeley.edu/talks/haotian-jiang-microsoft-research-redmond-2023-11-30
Optimization and Algorithm Design
Submodular function minimization (SFM) is a central problem in discrete optimization that has been studied extensively since the 1970s, with wide applications to many different areas of computer science, mathematics, economics, etc. Since Grotschel, Lovasz, and Schrijver's seminal work that SFM can be solved in (weakly and strongly) polynomial time, there has been significant effort in designing faster algorithms for SFM in various different settings of this problem. While tremendous progress has been made, many basic questions such as the correct oracle complexity of SFM remains widely open. In this talk, we cover recent progress on the design of SFM algorithms, which crucially leverages recent development of better convex optimization methods.