A linear bound on the diameter of the transportation polytope
type: Item
instance of: scholarly article
title: A linear bound on the diameter of the transportation polytope
zbMATH Open document ID: 1150.90008
author: Jan van den Heuvel
author: L. Stougie
author: Graham Brightwell
published in: Combinatorica
publication date: 2007-01-08T00:00:00Z
review text: The authors show that for any pair of vertices \(X,Y\) of an \(m \times n\) transportation polytope at most \(8(m+n-2)\) pivot steps are required to go from \(X\) to \(Y\). This improves the quadratic bound \(mn\) on the maximum diameter of a transpotation polytope given in \textit{V. A. Yemelichev, M. M. Kovalev} and \textit{M. K. Kravtsov} [Polytopes, Graphs and Optimization, Cambridge University Press (1984; Zbl 0523.52002)].
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C08
zbMATH DE Number: 5082293
zbMATH Keywords: transportation polytope
zbMATH Keywords: diameter
reviewed by: Rainer E. Burkard
MaRDI profile type: Publication
full work available at URL: s00493-006-0010-5
OpenAlex ID: W2111678432
DOI: 10.1007/S00493-006-0010-5
description: scientific article; zbMATH DE number 5082293