LOWER BOUNDS FOR THE MAXIMUM NUMBER OF SOLUTIONS GENERATED BY THE SIMPLEX METHOD(<Special Issue>SCOPE (Seminar on Computation and OPtimization for new Extensions))

スポンサーリンク

概要

• 論文の詳細を見る

• Kitahara and Mizuno [3] get upper bounds for the maximum number of different basic feasible solutions generated by the simplex method with the most negative pivoting rule. In this paper, we obtain lower bounds of the maximum number to show how tight the upper bounds are. Part of the results in this paper are shown in Kitahara and Mizuno [4] as a quick report without proof. They present a simple variant of Klee-Minty's LP and get a lower bound. In this paper, we explain and prove the properties of the variant more precisely. We also show a new lower bound by using a simple example of LP.

著者

• Kitahara Tomonari

  Tokyo Institute of Technology

• Kitahara Tomonari

  Tokyo Inst. Technol. Tokyo Jpn

• Mizuno Shinji

  Tokyo Inst. Technol. Tokyo Jpn

関連論文

• QUADRATIC AND CONVEX MINIMAX CLASSIFICATION PROBLEMS
• 2-C-8 Performance Assessment of Philippine Administrative Divisions by Means of Data Envelopment Analysis
• AN EXTENSION OF A MINIMAX APPROACH TO MULTIPLE CLASSIFICATION
• LOWER BOUNDS FOR THE MAXIMUM NUMBER OF SOLUTIONS GENERATED BY THE SIMPLEX METHOD(SCOPE (Seminar on Computation and OPtimization for new Extensions))

スポンサーリンク