Signature classes of transportation polytopes

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.