Lecture 9

The transportation problem and assignment problems are important problems, both practically and theoretically. They are simple without being trivial, and therefore are good problems on which to test new ideas about algorithmic methods.

I mentioned the fact that the Hirsch conjecture for the $n\times m$ Hitchcock transportation problem polytope states that no more than $m+n-1$ pivots should be needed to move between any two basic feasible solutions.

The diameter of a specific transportation polytope depends on the values of $n$, $m$, $s_i$s and $d_j$s, all integers. The Hirsch conjecture can be checked combinationally for small value of these. That has been done and the Hirsch conjecture has indeed been found to hold. (We allow pivot steps for which $\sum_{ij}x_{ij}c_{ij}$ does not decrease.)

A recent seminar on the subject is Kim's Transportation problem and the diameters of transportation polytopes (2015). Kim says that Hurkens has proved the upper bound $4(m+n-1)$. There is a folklore that Hurkens proved $3(m+n-1)$ in 2007, but this is in an unpublished paper. It is not hard to prove that the Hirsch conjecture holds for the special case $n=2$ and general $m$. I cannot recall whether or not it has been shown for $n=3$.

The assignment problem polytope has diameter 2 because every permutation is the product of two cycles, and applying a cyclic permutation to an assignment corresponds to a pivot step in the assignment problem. See On the assignment polytope, by Balinski and Russakoff.

The network simplex algorithm which we used in today's lecture to solve the transportation problem is not a polynomial time algorithm, but in practice it works very well. There do exist simplex-like pivoting algorithms for the transportation problem that run in polynomial time. I will explain next time a polynomial time algorithm for the special case of the assignment problem. This is the Hungarian algorithm, which solves the $n\times n$ assignment problem in time $O(n^3)$.

Lecture 8

The minimum cost flow problem (MCFP) is important because a huge number of problems are special cases of it. We saw in 8.5 that the longest-path problem can be viewed as a MCFP and leads to the critical path method, one of the oldest of all operational research techniques.

We have studied the solution of the MCFP by the network simplex algorithm. As with a general linear programming problem, the possibility of making a bad choice of pivots can give the algorithm a worse that polynomial running time. However, there do exist simplex algorithms which do run in polynomial time. See

James B. Orlin (1997). "A polynomial time primal network simplex algorithm for minimum cost flows". Mathematical Programming 78: 109–129.

Suppose $n$ and $m$ are the numbers of vertices and edges, respectively, and each cost is either $\infty$ or an integer bounded by $C$. Orlin describes an simplex-like pivoting algorithm with running $O\bigl(\min(n^2m \log nC, n^2m^2 \log n)\bigr)$.

Lecture 7

You will have seen that the details of the Ellipsoid algorithm are really quite intricate. I have tried to show you the key ideas in Lemmas 7.1-7.3, but have not dealt with the issue of approximating square roots in polynomial running time. If you have a question about the explanation or think you see an error in the notes, please let me know so I can fix it.

I think the proof of Lemma 7.3 is particularly cute for the way it uses the primal-dual theory of linear programming to show that $\text{P}=\emptyset\implies \text{P}_\epsilon=\emptyset$. Question 10 on Examples Sheet 1 is similar in spirit.

Remember that the importance of the Ellipsoid algorithm lies in its theoretical rather than practical. In practice, linear programs are solved by high quality implementations of the simplex algorithm or by an interior point method like Karamakar's method.

In Lemma 7.2 we used the fact that $Q\subset \mathbb{R}^n$, the convex hull of $n+1$ vectors, $v^0,v^1,\dotsc,v^n$, that do not lie in the same hyperplane has
$$ \text{vol}(Q)=\frac{1}{n!}\left| \det \left( \begin{array}{ccc} 1 & \cdots & 1 \\ v^0 & \cdots & v^n \end{array} \right)\right|. $$ The proof of this result is not for our course, but if you are interested see A Note on the Volume of a Simplex, P. Stein The American Mathematical Monthly Vol. 73, No. 3 (Mar., 1966), pp. 299-301