Recent Developments in Combinatorial Optimization

In the past several years, there has been a lot of progress on combinatorial optimization. Using techniques in convex optimization, geometry, spectral graph theory and randomization, researchers have developed provably faster algorithms for many classical problems such as linear programming and maximum flow problems. In this talk, I will discuss my work in this area and illustrate it through my recent result on the feasibility problem. Many optimization problems in computer science are shown to be polynomial-time-solvable by reducing it to the feasibility problem and then applying ellipsoid method. However, ellipsoid method is not very efficient. I will present an alternative, the first nearly cubic time algorithm for the feasibility problem. Furthermore, I will discuss how to use this to obtain faster algorithms for submodular minimization, matroid intersection and semidefinite programming.

Speaker Details

Yin Tat Lee is a PhD student in the department of mathematics at MIT, advised by Jonathan Kelner. His areas of research span convex optimization, convex optimization, spectral graph theory, and online algorithms. He is particularly interested in combining convex optimization and combinatorial techniques to design fast algorithms for classical computer science problems. He is one of the recipients of the Best Paper Award at SODA 2014 and FOCS 2014, as well as the Best Student Paper Award of FOCS 2014 and FOCS 2015.

Date:
Speakers:
Yin Tat Lee
Affiliation:
MIT