ISSN:
1436-4646
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract A class of polytopes is defined which includes the polytopes related to the assignment problem, the edge-matching problem on complete graphs, the multi-dimensional assignment problem, and many other set partitioning problems. Modifying some results due to Balas and Padberg, we give a constructive proof that the diameter of these polytopes is less than or equal to two. This result generalizes a result obtained by Balinski and Rusakoff in connection with the assignment problem. Furthermore, it is shown that the polytope associated with the travelling salesman problem has a diameter less than or equal to two. A weaker form of the Hirsch conjecture is also shown to be true for this polytope.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01585502
Permalink
