A strongly polynomial algorithm for a special class of linear programs

The authors extend the list of linear programming problems that are known to be solvable in strongly polynomial time to include a class of LPs which contains special cases of the generalized transshipment problem. The result is facilitated by exploiting some special properties associated with Leontief substitution systems and observing that a feasible solution to the system, Ax=b, x≥0, in which no variable appears in more than two equations, can be found in strongly polynomial time for b belonging to some set ¦[.