BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Tomonari Kitahara contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Recently, Chubanov proposed an interesting new polynomial-time algorithm for linear program. In this paper, we extend his algorithm to second-order cone programming.
In this short paper, we give an upper bound for the number of different basic feasible solutions generated by the simplex method for linear programming problems having optimal solutions. The bound is polynomial of the number of constraints, the number of variables, and the ratio between the minimum and the maximum values of all the positive elements of primal basic feasible solutions. When the primal problem is nondegenerate, it becomes a bound for the number of iterations. We show some basic results when it is applied to special linear programming problems. The results include strongly polynomiality of the simplex method for Markov Decision Problem by Ye and utilize its analysis.
Kitahara and Mizuno (2010) get two upper bounds for the number of different basic feasible solutions generated by Dantzig's simplex method. The size of the bounds highly depends on the ratio between the maximum and minimum values of all the positive elements of basic feasible solutions. In this paper, we show some relations between the ratio and the number of iterations by using an example of LP, which is a simple variant of Klee-Minty's LP. We see that the ratio for the variant is equal to the number of iterations by Dantzig's simplex method for solving it. This implies that it is impossible to get a better upper bound than the ratio. We also give improved results of the upper bounds.