Deeparnab Chakrabarty (Dartmouth)
Friday, August 4, 2017
Klaus 1116 East - 11:00 am
Title: Submodular Function Minimization via Continuous Optimization
Abstract:
Submodular functions are beautiful objects arising in many areas including computer science, probability, operations research, etc. They are set functions defined over subsets of an n-element universe with the property that f(A) + f(B) is at least f(union of A and B) + f(intersection of A and B). One paradigmatic problem is that of submodular function minimization: find the set which minimizes f with only oracle access to f. Amazingly, this can be done in polynomial time. Recently, continuous optimization techniques have given rise to fast algorithms for submodular function minimization (SFM).
A large part of the talk will be survey-ish, and time permitting I will talk about some recent results of mine in this line. The new results are joint work with Prateek Jain, Pravesh Kothari, Yin Tat Lee, Aaron Sidford, and Sam Wong.
----------------------------------------------------------------
Videos of recent talks are available at: https://smartech.gatech.edu/handle/1853/46836
Click here to subscribe to the seminar email list: arc-colloq@cc.gatech.edu
]]>