Graph theory seminar - Christopher Price

Simple Submodular Function Minimization

Abstract:

In combinatorics, submodular functions abound. Some common examples include the cut capacity function of a graph and the rank function of a matroid. Many classical problems in combinatorial optimization can be formulated as an instance of submodular function minimization. While polynomial-time algorithms have long been known, due to recent developments in artificial intelligence and machine learning, there is a resurgence of interest in algorithms to solve the problem. This talk will discuss a remarkably simple algorithm for submodular function minimization, based on the work of Frank and Mikl\"os.