We investigate the diameter of the polytope arising in the n-city symmetric traveling salesman problem (TSP) and perfect matching polytopes. Grötschel and Padberg [The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, Wiley-Intersci. Ser. Discrete Math., E. Lawler et al., eds., John Wiley, Chichester, 1985, pp. 251--305] conjectured that the diameter of the symmetric TSP polytope is 2, independent of n. We constructively show that its diameter is at most 4, for all $n \geq 3$. Our result also shows that the diameter of the perfect 2-matching polytope is at most 6, for every $n \geq 3$.

This paper provides a very simple two-approximation algorithm for two NP-hard problems that arise in electronic circuit design. To our knowledge, this is the best approximation bound known for these problems. In addition, the simplicity of the proposed algorithm makes it attractive for real-time applications for similar problems in areas such as telecommunications and parallel processing.

The dual linear programs for the transhipment problem over a directed graph, $G = \{ N,E\} $, are shown to have polyhedra with properties that make them well suited to vertex visiting solution techniques, like the simplex method. In particular, nondegenerate cases are shown to have feasible regions with considerably fewer extreme points than the feasible sets for primal problems. The adjacency structure of feasible bases is also shown to be quite favorable. In fact, the Hirsch Conjecture is valid when the network is complete. A dual-based simplex method for cases of the transhipment problem, which include the shortest paths problem, is presented that finds an optimal solution in no more than $\text{Min}( | E | - | N | + 1, | N | | N - 1 |/2 )$ pivots.