Signature classes of transportation polytopes |
| |
Authors: | M. L. Balinski Fred J. Rispoli |
| |
Affiliation: | (1) C.N.R.S., Laboratoire d'Econométrie de l'Ecole Polytechnique, 1 rue Descartes, 75005 Paris, France;(2) Department of Mathematics, Dowling College, Oakdale, NY, USA |
| |
Abstract: | Signature algorithms solve certain classes of transportation problems in a number of steps bounded by the diameter of the dual polyhedron. The class of problems to which signature algorithms may be applied—the signature classes of the title—are characterized, and the monotonic Hirsch conjecture is shown to hold for them. In addition, certain more precise results are given for different cases. Finally, it is explained why a supposed proof of the Hirsch conjecture for all transportation polytopes is incomplete and apparently irremedial.Dedicated with affection to Philip Wolfe on the occasion of his 65th birthday. |
| |
Keywords: | Transportation problem polytope Hirsch conjecture diameter Hirsch-path strongly polynomial algorithm |
本文献已被 SpringerLink 等数据库收录! |
|