# Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | 2018 | 2019 | 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* x *n* TP has *m* supply points and *n *demand points. Each supply point *i* holds a quantity *r _{i}*, and each demand point

*j*wants a quantity

*c*, where the total supply is equal to the total demand. Suppose we must transport non-negative quantities

_{j}*x*from nodes

_{ij}*i*to

*j*so that all demands are met. The collection of all feasible solutions forms a convex polytope, the

__transportation polytope__.<br> We are interested in the diameter of the skeleton (the edge-graph) of

*T**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

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