The Complexity of Zadeh's Pivot Rule (Record no. 70986)
[ view plain ]
| 000 -LEADER | |
|---|---|
| fixed length control field | 02515naaaa2200325uu 4500 |
| 001 - CONTROL NUMBER | |
| control field | https://directory.doabooks.org/handle/20.500.12854/64442 |
| 005 - DATE AND TIME OF LATEST TRANSACTION | |
| control field | 20220220063650.0 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 5206 |
| 020 ## - INTERNATIONAL STANDARD BOOK NUMBER | |
| International Standard Book Number | 9783832552060 |
| 024 7# - OTHER STANDARD IDENTIFIER | |
| Standard number or code | 10.30819/5206 |
| Terms of availability | doi |
| 041 0# - LANGUAGE CODE | |
| Language code of text/sound track or separate title | English |
| 042 ## - AUTHENTICATION CODE | |
| Authentication code | dc |
| 072 #7 - SUBJECT CATEGORY CODE | |
| Subject category code | PBT |
| Source | bicssc |
| 100 1# - MAIN ENTRY--PERSONAL NAME | |
| Personal name | Vincent Hopp, Alexander |
| Relationship | auth |
| 245 10 - TITLE STATEMENT | |
| Title | The Complexity of Zadeh's Pivot Rule |
| 260 ## - PUBLICATION, DISTRIBUTION, ETC. | |
| Place of publication, distribution, etc. | Berlin/Germany |
| Name of publisher, distributor, etc. | Logos Verlag Berlin |
| Date of publication, distribution, etc. | 2020 |
| 300 ## - PHYSICAL DESCRIPTION | |
| Extent | 1 electronic resource (335 p.) |
| 506 0# - RESTRICTIONS ON ACCESS NOTE | |
| Terms governing access | Open Access |
| Source of term | star |
| Standardized terminology for access restriction | Unrestricted online access |
| 520 ## - SUMMARY, ETC. | |
| Summary, etc. | 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. |
| 540 ## - TERMS GOVERNING USE AND REPRODUCTION NOTE | |
| Terms governing use and reproduction | Creative Commons |
| Use and reproduction rights | https://creativecommons.org/licenses/by-nc-nd/4.0/ |
| Source of term | cc |
| -- | https://creativecommons.org/licenses/by-nc-nd/4.0/ |
| 546 ## - LANGUAGE NOTE | |
| Language note | English |
| 650 #7 - SUBJECT ADDED ENTRY--TOPICAL TERM | |
| Topical term or geographic name entry element | Probability & statistics |
| Source of heading or term | bicssc |
| 653 ## - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Optimierung, Optimization |
| 653 ## - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Komplexität, Complexity |
| 653 ## - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Lineare Programmierung, Linear programming |
| 653 ## - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Simplexalgorithmus, Simplex algorithm |
| 653 ## - INDEX TERM--UNCONTROLLED | |
| Uncontrolled term | Pivotregel, Pvot rule |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Host name | www.oapen.org |
| Uniform Resource Identifier | <a href="https://www.logos-verlag.de/ebooks/OA/978-3-8325-5206-0.pdf">https://www.logos-verlag.de/ebooks/OA/978-3-8325-5206-0.pdf</a> |
| Access status | 0 |
| Public note | DOAB: download the publication |
| 856 40 - ELECTRONIC LOCATION AND ACCESS | |
| Host name | www.oapen.org |
| Uniform Resource Identifier | <a href="https://directory.doabooks.org/handle/20.500.12854/64442">https://directory.doabooks.org/handle/20.500.12854/64442</a> |
| Access status | 0 |
| Public note | DOAB: description of the publication |
No items available.