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

DOI10.1080/10556788.2016.1208748MaRDI QIDQ2829586zbMATH OpenOpenAlexFDO

Authors Shinji Mizuno

Publication date 8 November 2016

Published in Optimization Methods \& Software (Search for Journal in Brave)

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

zbMATH Keywords

linear programmingsimplex methodstrongly polynomial algorithmtotally unimodular matrix

Mathematics Subject Classification ID

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

Recommendations

• Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm
• The simplex method is strongly polynomial for deterministic Markov decision processes
• The simplex method is strongly polynomial for deterministic Markov decision processes
• A primal-simplex based Tardos' algorithm
• An alternative proof of a PTAS for fixed-degree polynomial optimization over the simplex
• scientific article; zbMATH DE number 1161055
• A Strongly Polynomial Algorithm for a Special Class of Linear Programs
• A new revised simplex method for degenerate linear programs
• A genuinely polynomial primal simplex algorithm for the assignment problem
• A concise way of determination for LP initial feasible basis of simplex method

Cites work

• A Strongly Polynomial Algorithm to Solve Combinatorial Linear Programs
• A bound for the number of different basic solutions generated by the simplex method
• A new polynomial-time algorithm for linear programming
• A strongly polynomial simplex method for the linear fractional assignment problem
• New Finite Pivoting Rules for the Simplex Method
• On the number of solutions generated by the dual simplex method
• The simplex and policy-iteration methods are strongly polynomial for the Markov decision problem with a fixed discount rate

Cited in

(2)

• Short simplex paths in lattice polytopes
• A primal-simplex based Tardos' algorithm

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2829586)