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

DOI10.1080/10556788.2016.1208748zbMATH Open1355.90044OpenAlexW2488992236MaRDI QIDQ2829586FDOQ2829586

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)

Cites Work

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

Cited In (1)

• Short simplex paths in lattice polytopes

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• A Strongly Polynomial Algorithm for a Special Class of Linear Programs 👍 👎
• Title not available (Why is that?) 👍 👎
• A genuinely polynomial primal simplex algorithm for the assignment problem 👍 👎
• A concise way of determination for LP initial feasible basis of 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

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