The Complexity of Zadeh’s Pivot Rule
By (author) Alexander Vincent Hopp
Paperback (Published)
(November 2020)
ISBN: 9783832552060
5.71 x 8.27 inches
Price: $81.00
Out of stock
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.
- By (author) Alexander Vincent Hopp
Similar Books
![Book cover: Transitive Media [Philosophy]](https://isd.stisonbooks.com/images/books/native/9781804132326.jpg?asset_id=66970)
Care in an Era of New Technologies and Artificial Intelligence
Relationships in a Connected World
Volume 14
Buchblogs zwischen Passion und Profession
Zur Diskursivierung digitaler literaturbezogener Anschlusskommunikation als Arbeit
Die Einführung ins richtige Handeln in der Arithmetik (Madḫal ar-rašad ilā ʿilm al-ʿadad) von al-Qalaṣādī (st. 1486)
Bearbeitung und Einordnung in die maġribinische Mathematikgeschichte
Volume 19
Digitale Medien und Religionsunterricht
Ein domänenspezifischer Beitrag zu einer kritischen Medienbildung unter Berücksichtigung medien-, bildungs- und lerntheoretischer Perspektiven
Ein Glucksritter als Wegbereiter der Motorisierung
Der Basler Kaufmann Eduard Burckhardt (1847-1897)
Partizipative Produktentwicklung in der Modeindustrie
Methoden, Vorgehensmodelle und ihre Anwendung in der Wertschöpfung smarter Outdoorbekleidung
Heterarchical Production Planning and Control Architectures in the Context of Industry 4.0
Complexity-based Selection and Guidance for Implementation
Volume 67
Proceedings of the 7th Symposium of the Hellenic Society for Archaeometry
Archaeology Archaeometry: 30 Years Later
I disegni e i discorsi di Giovanni Antonio Nigrone vol. I
fontanaro e ingegniero de acqua (1585-1609 ca.)
Volume 481
I disegni e i discorsi di Giovanni Antonio Nigrone vol. II
Fontanaro e ingegniero de acqua (1585-1609 ca.)
Volume 497
