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.