# How fast can we solve a totally unimodular integer linear program?

(This is a follow-up to this question and its answer.)

I have the following totally unimodular (TU) integer linear program (ILP). Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive integers given as part of the input. A specified subset of the variables $x_{ij}$ is set to zero, and the rest can take positive integral values:

Minimize

$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$

Subject to:

$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$

$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

The coefficient matrix of the standard form is a $(2\ell+m)\times \ell m$ matrix with entries from ${-1,0,1}$.

My question is:

What are the best upper bounds known for the running time of polynomial-time algorithms that solve such an ILP? Could you point me to some references on this?

I did some searching, but at most places they stop with saying that a TU ILP can be solved in polynomial time using polynomial-time algorithms for LP. One thing that looked promising is a 1986 paper by Tardos [1] where she proves that such problems can be solved in time polynomial in the size of the coefficient matrix. As far as I could figure out from the paper, however, the running time of that algorithm depends in turn on the running time of a polynomial-time algorithm for solving LP.

Do we know of algorithms that solve this special case (of TU ILP) significantly faster than the general algorithms that solve the LP problem?

If not,

Which algorithm for LP would solve such an ILP the fastest (in an asymptotic sense)?

[1] A strongly polynomial algorithm to solve combinatorial linear programs, Eva Tardos, Operations Research 34(2), 1986

• As pointed out by the answer you cite to your previous post, your problem is a special case of the transportation problem, which is in turn a special case of minimum-cost flow. See here and here for posts asking for fast algorithms for these two problems. – Neal Young Aug 19 '17 at 22:58

You might be able to derive better bounds from the general LP algorithm in the paper "Linear Programming in $O([n^3/\ln n]L)$ Operations" (here).