Exponential lower bounds for history-based simplex pivot rules on abstract cubes
OPEN ACCESS
Loading...
Author / Producer
Date
2017
Publication Type
Conference Paper
ETH Bibliography
yes
Citations
Altmetric
OPEN ACCESS
Data
Rights / License
Abstract
The behavior of the simplex algorithm is a widely studied subject. Specifically, the question of the existence of a polynomial pivot rule for the simplex algorithm is of major importance. Here, we give exponential lower bounds for three history-based pivot rules. Those rules decide their next step based on memory of the past steps. In particular, we study Zadeh's least entered rule, Johnson's least-recently basic rule and Cunningham's least-recently considered (or round-robin) rule. We give exponential lower bounds on Acyclic Unique Sink Orientations of the abstract cube, for all of these pivot rules. For Johnson's rule our bound is the first superpolynomial one in any context; for Zadeh's it is the first one for AUSO. Those two are our main results.
Permanent link
Publication status
published
External links
Book title
25th Annual European Symposium on Algorithms (ESA 2017)
Volume
87
Pages / Article No.
69
Publisher
Schloss Dagstuhl – Leibniz-Zentrum für Informatik
Event
25th Annual European Symposium on Algorithms (ESA 2017)
Edition / version
Methods
Software
Geographic location
Date collected
Date created
Subject
pivot rule; lower bound; exponential; unique sink orientation; zadeh
Organisational unit
03457 - Welzl, Emo (emeritus) / Welzl, Emo (emeritus)