Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 12.01.2012 at 12:20 in S6, there is the following noon lecture:

Strongly polynomial algorithm for a class of minimum-cost flow problems with separable convex objectives

Laszlo Vegh

Eötvös Loránd University

Abstract

A well-studied nonlinear extension of the minimum-cost flow problem is to minimize the objective \sum_{ij\in E} C_{ij}(f_{ij}) over feasible flows f, where on each arc ij of the network, C_{ij} is a convex function. We give a strongly polynomial algorithm for finding an exact optimal solution for a broad class of such problems. The class includes convex quadratic objectives; thereby we give the first strongly polynomial algorithms for separable quadratic minimum-cost flows, settling a long-standing open question. Further applications include market equilibrium problem, in particular, we give the first strongly polynomial algorithm for Fisher's market with spending constraint utilities.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010