On the number of solutions generated by the dual simplex method

DOI10.1016/J.ORL.2012.01.004zbMATH Open1252.90044OpenAlexW1964500497MaRDI QIDQ439907FDOQ439907

Authors: Tomonari Kitahara, Shinji Mizuno 

Publication date: 17 August 2012

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

Full work available at URL: https://doi.org/10.1016/j.orl.2012.01.004

Recommendations

• On the number of solutions generated by Dantzig's simplex method for LP with bounded variables
• An upper bound for the number of different solutions generated by the primal simplex method with any selection rule of entering variables
• A bound for the number of different basic solutions generated by the simplex method
• On the number of solutions generated by the simplex method for LP
• Lower bounds for the maximum number of solutions generated by the simplex method

zbMATH Keywords

maximum flow problembasic feasible solutionsdual simplex method

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?)
• 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
• Klee-Minty's LP and upper bounds for Dantzig's simplex method
• On the number of solutions generated by Dantzig's simplex method for LP with bounded variables

Cited In (6)

• Short simplex paths in lattice polytopes
• The simplex method using Tardos' basic algorithm is strongly polynomial for totally unimodular LP under nondegeneracy assumption
• On the Number of Solutions Generated by the Simplex Method for LP
• A primal-simplex based Tardos' algorithm
• On the number of solutions generated by Dantzig's simplex method for LP with bounded variables
• A bound for the number of different basic solutions generated by the simplex method

This page was built for publication: On the number of solutions generated by the dual simplex method

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