external_content.pdf

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...

Πλήρης περιγραφή

Λεπτομέρειες βιβλιογραφικής εγγραφής
Γλώσσα:English
Έκδοση: Logos Verlag Berlin 2022
id oapen-20.500.12657-56796
record_format dspace
spelling oapen-20.500.12657-567962023-01-31T18:45:33Z The Complexity of Zadeh's Pivot Rule Hopp, Alexander Vincent Computers Computer Science bic Book Industry Communication::U Computing & information technology::UY Computer science 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. 2022-06-18T05:38:39Z 2022-06-18T05:38:39Z 2020 book 9783832552060 https://library.oapen.org/handle/20.500.12657/56796 eng application/pdf n/a external_content.pdf Logos Verlag Berlin Logos Verlag Berlin https://doi.org/10.30819/5206 https://doi.org/10.30819/5206 1059eef5-b798-421c-b07f-c6a304d3aec8 b818ba9d-2dd9-4fd7-a364-7f305aef7ee9 9783832552060 Knowledge Unlatched (KU) Logos Verlag Berlin Knowledge Unlatched open access
institution OAPEN
collection DSpace
language English
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.
title external_content.pdf
spellingShingle external_content.pdf
title_short external_content.pdf
title_full external_content.pdf
title_fullStr external_content.pdf
title_full_unstemmed external_content.pdf
title_sort external_content.pdf
publisher Logos Verlag Berlin
publishDate 2022
_version_ 1771297401425887232