A primal-simplex based Tardos' algorithm

DOI10.1016/J.ORL.2015.10.002zbMATH Open1408.90177arXiv1409.1999OpenAlexW1758756115MaRDI QIDQ1785451FDOQ1785451

Authors: Shinji Mizuno, Noriyoshi Sukegawa, Antoine Deza 

Publication date: 28 September 2018

Published in: Operations Research Letters (Search for Journal in Brave)

Abstract: 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 to solve the auxiliary problems. The proposed algorithm is strongly polynomial if the coefficient matrix is totally unimodular and the auxiliary problems are non-degenerate.

Full work available at URL: https://arxiv.org/abs/1409.1999

Recommendations

• scientific article; zbMATH DE number 6938247
• The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
• A dual version of Tardos's algorithm for linear programming
• Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos' algorithm
• scientific article; zbMATH DE number 1859212

zbMATH Keywords

simplex methodstrongly polynomial algorithmtotal unimodularityTardos' algorithm

Mathematics Subject Classification ID

Linear programming (90C05) Extreme-point and pivoting methods (90C49)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A strongly polynomial minimum cost circulation algorithm
• 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 dual version of Tardos's algorithm for linear programming

Cited In (6)

• Title not available (Why is that?)
• A dual version of Tardos's algorithm for linear programming
• The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
• Title not available (Why is that?)
• An asymptotically improved upper bound on the diameter of polyhedra
• Improving bounds on the diameter of a polyhedron in high dimensions

This page was built for publication: A primal-simplex based Tardos' algorithm

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