The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption

DOI10.1080/10556788.2016.1208748zbMath1355.90044OpenAlexW2488992236MaRDI QIDQ2829586

Shinji Mizuno

Publication date: 8 November 2016

Published in: Optimization Methods and Software (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/10556788.2016.1208748

zbMATH Keywords

linear programmingsimplex methodtotally unimodular matrixstrongly polynomial algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Number-theoretic algorithms; complexity (11Y16) Extreme-point and pivoting methods (90C49)

Related Items (1)

Short simplex paths in lattice polytopes

Cites Work

• On the number of solutions generated by the dual simplex method
• A new polynomial-time algorithm for linear programming
• A strongly polynomial simplex method for the linear fractional assignment problem
• A bound for the number of different basic solutions generated by the simplex method
• The Simplex and Policy-Iteration Methods Are Strongly Polynomial for the Markov Decision Problem with a Fixed Discount Rate
• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• New Finite Pivoting Rules for the Simplex Method

This page was built for publication: The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption