Noon lecture

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

On 04.12.2006 at 12:20 in S1, there is the following noon lecture:

On the Diameter of the Transportation Polytope

Jan van den Heuvel

London School of Economics

Abstract

The transportation problem (TP) is a classic problem in operations research. The m&nbsp;x&nbsp;n TP has m supply points and n demand points. Each supply point i holds a quantity ri, and each demand point j wants a quantity cj, where the total supply is equal to the total demand. Suppose we must transport non-negative quantities xij from nodes i to j so that all demands are met. The collection of all feasible solutions forms a convex polytope, the transportation polytope T.<br> We are interested in the diameter of the skeleton (the edge-graph) of T. In the talk I give some motivation why this is an interesting problem. We also show how the problem to find the diameter can be formulated completely in terms of operations on subgraphs of edge-weighted

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