Improvement of Kalai-Kleitman bound for the diameter of a polyhedron

Recently, Todd got a new bound on the diameter of a polyhedron using an analysis due to Kalai and Kleitman in 1992. In this short note, we prove that the bound by Todd can further be improved. Although our bound is not valid when the dimension is 1 or 2, it is tight when the … Read more

A primal-simplex based Tardos’ algorithm

In the mid-eighties Tardos proposed a strongly polynomial algorithm for solving linear programming problems for which the size of the coefficient matrix is polynomially bounded by the dimension. Combining Orlin’s primal-based modification and Mizuno’s use of the simplex method, we introduce a modification of Tardos’ algorithm considering only the primal problem and using simplex method … Read more