| 000 | 02691nam a22003617a 4500 | ||
|---|---|---|---|
| 003 | KnowledgeUnlatched | ||
| 005 | 20210303104712.0 | ||
| 006 | m o d | ||
| 007 | cr u|||||||||| | ||
| 008 | 210129p20202021xx o u00| u eng d | ||
| 037 | _5BiblioBoard | ||
| 245 | 0 | 4 |
_aThe Complexity of Zadeh's Pivot Rule _cAlexander Vincent Hopp. |
| 020 | _a9783832552060 | ||
| 024 | 8 | _ahttps://doi.org/10.30819/5206 | |
| 029 | 1 | _ahttps://library.biblioboard.com/ext/api/media/4fe41f5a-625b-47f8-bbb5-3e2ced4dc29f/assets/thumbnail.jpg | |
| 040 |
_aScCtBLL _cScCtBLL |
||
| 100 | 1 |
_aHopp, Alexander Vincent _eauthor. |
|
| 264 | 1 | _bLogos Verlag Berlin, | |
| 300 | _a1 online resource (1 p.) | ||
| 506 | 0 |
_aAccess copy available to the general public. _fUnrestricted _2star |
|
| 520 | _aThe 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. | ||
| 588 | 0 | _aDescription based on print version record. | |
| 650 | 7 |
_aTechnology & Engineering / Agriculture _2bisacsh |
|
| 650 | 7 |
_aComputers / Computer Science _2bisacsh |
|
| 650 | 7 |
_aMathematics _2bisacsh |
|
| 650 | 0 | _aMathematics | |
| 655 | 0 | _aElectronic books. | |
| 758 |
_iIs found in: _aKnowledge Unlatched _1https://openresearchlibrary.org/module/2774bc74-146a-484f-a7ba-ab1d6a09bbfb |
||
| 856 | 4 | 0 |
_uhttps://openresearchlibrary.org/content/4fe41f5a-625b-47f8-bbb5-3e2ced4dc29f _zView this content on Open Research Library. _70 |
| 999 |
_c32341 _d32341 |
||