A bound for the number of different basic solutions generated by the simplex method
From MaRDI portal
Publication:1942281
DOI10.1007/s10107-011-0482-yzbMath1262.90086arXiv1101.3820OpenAlexW2133159317MaRDI QIDQ1942281
Tomonari Kitahara, Shinji Mizuno
Publication date: 18 March 2013
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1101.3820
Linear programming (90C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Extreme-point and pivoting methods (90C49)
Related Items (20)
On Augmentation Algorithms for Linear and Integer-Linear Programming: From Edmonds--Karp to Bland and Beyond ⋮ Complexity bounds for approximately solving discounted MDPs by value iterations ⋮ On the Number of Solutions Generated by the Simplex Method for LP ⋮ A divide-and-conquer algorithm for binary matrix completion ⋮ Monotone diameter of bisubmodular polyhedra ⋮ On the number of solutions generated by the dual simplex method ⋮ A double-pivot simplex algorithm and its upper bounds of the iteration numbers ⋮ A scaling algorithm for optimizing arbitrary functions over vertices of polytopes ⋮ Klee-Minty's LP and upper bounds for Dantzig's simplex method ⋮ Modified policy iteration algorithms are not strongly polynomial for discounted dynamic programming ⋮ A primal-simplex based Tardos' algorithm ⋮ Computing Kitahara-Mizuno's bound on the number of basic feasible solutions generated with the simplex algorithm ⋮ Steepest-edge rule and its number of simplex iterations for a nondegenerate LP ⋮ The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption ⋮ AN UPPER BOUND FOR THE NUMBER OF DIFFERENT SOLUTIONS GENERATED BY THE PRIMAL SIMPLEX METHOD WITH ANY SELECTION RULE OF ENTERING VARIABLES ⋮ On the reduction of total‐cost and average‐cost MDPs to discounted MDPs ⋮ On the Length of Monotone Paths in Polyhedra ⋮ Pivot Rules for Circuit-Augmentation Algorithms in Linear Optimization ⋮ A scaling-invariant algorithm for linear programming whose running time depends only on the constraint matrix ⋮ Short simplex paths in lattice polytopes
Cites Work
This page was built for publication: A bound for the number of different basic solutions generated by the simplex method
