Strong polynomiality of the simplex method for totally unimodular linear programming problems
Linear programming is the most fundamental optimization problem with applications in many areas including engineering, management, and economics.
É. Tardos of Cornell University proposed a strongly polynomial algorithm for combinatorial linear programming problems and T. Kitahara and S. Mizuno at Tokyo Institute of Technology have obtained a new bound for the number of distinct solutions generated by the simplex method.
It is known that the simplex method requires an exponential number of iterations for some special linear programming instances. Hence the method is neither polynomial nor a strongly-polynomial algorithm for general linear programming problems.
The researchers showed that the simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular linear programming problems, if the problems are nondegenerate.
These findings give a theoretical background as to why the simplex method could solve a large scale linear programming problem efficiently.