- 【Updated on May 12, 2025】 Integration of CiNii Dissertations and CiNii Books into CiNii Research
- Trial version of CiNii Research Automatic Translation feature is available on CiNii Labs
- Suspension and deletion of data provided by Nikkei BP
- Regarding the recording of “Research Data” and “Evidence Data”
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 Tomonari
- Tokyo Institute of Technology
-
- Mizuno Shinji
- Tokyo Institute of Technology
Bibliographic Information
- Other Title
-
- LOWER BOUNDS FOR THE MAXIMUM NUMBER OF SOLUTIONS GENERATED BY THE SIMPLEX METHOD
Search this article
Description
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.
Journal
-
- Journal of the Operations Research Society of Japan
-
Journal of the Operations Research Society of Japan 54 (4), 191-200, 2011
The Operations Research Society of Japan
- Tweet
Details 詳細情報について
-
- CRID
- 1390282679086610304
-
- NII Article ID
- 110008897241
-
- NII Book ID
- AA00703935
-
- ISSN
- 21888299
- 04534514
-
- NDL BIB ID
- 023392111
-
- Text Lang
- en
-
- Article Type
- journal article
-
- Data Source
-
- JaLC
- NDL Search
- Crossref
- CiNii Articles
- KAKEN
- OpenAIRE
-
- Abstract License Flag
- Disallowed