The Complexity of Zadeh's Pivot Rule
The Simplex algorithm is one of the most important algorithms in discrete optimization, and is the most used algorithm for solving linear programs in practice. In the last 50 years, several pivot rules for this algorithm have been proposed and studied. For most deterministic pivot rules, exponential...
Сохранить в:
| Главный автор: | |
|---|---|
| Формат: | Online |
| Язык: | английский |
| Опубликовано: |
Logos Verlag Berlin
2021
|
| Предметы: | |
| Online-ссылка: | ONIX_20210408_9783832552060_84 |
| Метки: |
Нет меток, Требуется 1-ая метка записи!
|
| _version_ | 1869520309083701248 |
|---|---|
| author | Vincent Hopp, Alexander |
| author_browse | Vincent Hopp, Alexander |
| author_facet | Vincent Hopp, Alexander |
| author_sort | Vincent Hopp, Alexander |
| collection | Directory of Open Access Books |
| description | The Simplex algorithm is one of the most important algorithms in discrete optimization, and is the most used algorithm for solving linear programs in practice. In the last 50 years, several pivot rules for this algorithm have been proposed and studied. For most deterministic pivot rules, exponential lower bounds were found, while a probabilistic pivot rule exists that guarantees termination in expected subexponential time. One deterministic pivot rule that is of special interest is Zadeh's pivot rule since it was the most promising candidate for a polynomial pivot rule for a long time. In 2011, Friedmann proved that this is not true by providing an example forcing the Simplex algorithm to perform at least a subexponential number of iterations in the worst case when using Zadeh's pivot rule. Still, it was not known whether Zadeh's pivot rule might achieve subexponential worst case running time. Next to analyzing Friedmann's construction in detail, we develop the first exponential lower bound for Zadeh's pivot rule. This closes a long-standing open problem by ruling out this pivot rule as a candidate for a deterministic, subexponential pivot rule in several areas of linear optimization and game theory. |
| format | Online |
| id | doab-20.500.12854ir-64442 |
| institution | Directory of Open Access Books |
| language | eng |
| publishDate | 2021 |
| publishDateRange | 2021 |
| publishDateSort | 2021 |
| publisher | Logos Verlag Berlin |
| publisherStr | Logos Verlag Berlin |
| record_format | ojs |
| spelling | doab-20.500.12854ir-644422024-04-04T14:41:13Z The Complexity of Zadeh's Pivot Rule Vincent Hopp, Alexander Optimierung, Optimization Komplexität, Complexity Lineare Programmierung, Linear programming Simplexalgorithmus, Simplex algorithm Pivotregel, Pvot rule thema EDItEUR::P Mathematics and Science::PB Mathematics::PBT Probability and statistics The Simplex algorithm is one of the most important algorithms in discrete optimization, and is the most used algorithm for solving linear programs in practice. In the last 50 years, several pivot rules for this algorithm have been proposed and studied. For most deterministic pivot rules, exponential lower bounds were found, while a probabilistic pivot rule exists that guarantees termination in expected subexponential time. One deterministic pivot rule that is of special interest is Zadeh's pivot rule since it was the most promising candidate for a polynomial pivot rule for a long time. In 2011, Friedmann proved that this is not true by providing an example forcing the Simplex algorithm to perform at least a subexponential number of iterations in the worst case when using Zadeh's pivot rule. Still, it was not known whether Zadeh's pivot rule might achieve subexponential worst case running time. Next to analyzing Friedmann's construction in detail, we develop the first exponential lower bound for Zadeh's pivot rule. This closes a long-standing open problem by ruling out this pivot rule as a candidate for a deterministic, subexponential pivot rule in several areas of linear optimization and game theory. 2021-04-08T15:35:12Z 2021-04-08T15:35:12Z 2020 book ONIX_20210408_9783832552060_84 9783832552060 https://directory.doabooks.org/handle/20.500.12854/64442 eng image/jpeg Attribution-NonCommercial-NoDerivatives 4.0 International https://www.logos-verlag.de/cgi-bin/engbuchmid?isbn=5206&lng=eng&id= https://www.logos-verlag.de/ebooks/OA/978-3-8325-5206-0.pdf Logos Verlag Berlin Logos Verlag Berlin 10.30819/5206 10.30819/5206 04b263a1-7fba-4491-9eae-1c394ac42fc3 9783832552060 Logos Verlag Berlin 335 Berlin/Germany open access |
| spellingShingle | Optimierung, Optimization Komplexität, Complexity Lineare Programmierung, Linear programming Simplexalgorithmus, Simplex algorithm Pivotregel, Pvot rule thema EDItEUR::P Mathematics and Science::PB Mathematics::PBT Probability and statistics Vincent Hopp, Alexander The Complexity of Zadeh's Pivot Rule |
| title | The Complexity of Zadeh's Pivot Rule |
| title_full | The Complexity of Zadeh's Pivot Rule |
| title_fullStr | The Complexity of Zadeh's Pivot Rule |
| title_full_unstemmed | The Complexity of Zadeh's Pivot Rule |
| title_short | The Complexity of Zadeh's Pivot Rule |
| title_sort | complexity of zadeh s pivot rule |
| topic | Optimierung, Optimization Komplexität, Complexity Lineare Programmierung, Linear programming Simplexalgorithmus, Simplex algorithm Pivotregel, Pvot rule thema EDItEUR::P Mathematics and Science::PB Mathematics::PBT Probability and statistics |
| topic_facet | Optimierung, Optimization Komplexität, Complexity Lineare Programmierung, Linear programming Simplexalgorithmus, Simplex algorithm Pivotregel, Pvot rule thema EDItEUR::P Mathematics and Science::PB Mathematics::PBT Probability and statistics |
| url | ONIX_20210408_9783832552060_84 |
| work_keys_str_mv | AT vincenthoppalexander thecomplexityofzadehspivotrule AT vincenthoppalexander complexityofzadehspivotrule |