Title: Approximately solving linear programs with applications to submodular function minimization 

<P>
Fabian Chudak<BR>

<p>
Abstract: <BR>

The talk will cover recent results on efficient decomposition methods for solving large scale linear programs and their applications. The first part of the talk will be devoted to introduce the mathematical model, as well as, recent numerically and provably efficient methods to solve it. Our results build mostly on recent results of Nesterov. 
The second part of the talk will focus on recent applications of the methods to combinatorial problems with submodular penalties. Because of their economical interpretations, these problems have received plenty of attention in the theoretical computer science community in recent years. Our results here make a novel use of the Lovasz extension of a submodular function. 
Throughout the talk, I will focus on the maximum concurrent multicommodity flow problem and the uncapacitated facility location problem (with submodular penalties) as the main examples of the techniques. 

<p>
This talk is mostly based on two papers, one with Vania Eleuterio (IPCO05) and one with Kiyohito Nagano (SODA07).