Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm

DOI10.1007/s11590-018-1276-4zbMath1402.90085OpenAlexW2804559392MaRDI QIDQ723482

Yoshio Sano, Takahito Kuno, Takahiro Tsuruda

Publication date: 31 July 2018

Published in: Optimization Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11590-018-1276-4

zbMATH Keywords

linear programmingsimplex algorithmNP-hardnessbasic feasible solutionsnumber of iterations

Mathematics Subject Classification ID

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

Related Items

Monotone diameter of bisubmodular polyhedra, On the Length of Monotone Paths in Polyhedra, Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization

Uses Software

• CLP
• NETLIB LP Test Set

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new polynomial-time algorithm for linear programming
• Pivot rules for linear programming: A survey on recent theoretical developments
• 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
• The Complexity of the Simplex Method
• Polynomial algorithms in linear programming
• Reducibility among Combinatorial Problems
• On Simplex Pivoting Rules and Complexity Theory
• The maximum numbers of faces of a convex polytope