Recent Progress on Submodular Function Minimization

Explore recent advancements in submodular function minimization (SFM) algorithms in this 32-minute lecture by Haotian Jiang from Microsoft Research, Redmond. Delve into the central problem of discrete optimization, tracing its extensive study since the 1970s and its wide-ranging applications across computer science, mathematics, and economics. Examine the progress made since Grotschel, Lovasz, and Schrijver's seminal work on polynomial-time SFM solutions, and investigate ongoing efforts to design faster algorithms for various SFM settings. Discover how recent developments in convex optimization methods have been crucial in advancing SFM algorithm design, while considering open questions such as the correct oracle complexity of SFM. Gain insights into this fundamental area of optimization and algorithm design through this comprehensive overview of recent progress in the field.