ON FLAWS IN THE EXPONENTIAL LOWER BOUNDS FOR ZADEH’S LEAST-ENTERED PIVOT RULE 1
DOI:
https://doi.org/10.61841/skzsny80Abstract
In 2011, Friedmann [F 7] claimed to have proved that pathological linear programs existed for which the Simplex method using Zadeh’s “least-entered” rule [Z 14] would take an exponential number of pivots. In 2019, Disser and Hopp [DH 5] argued that there were errors in Friedmann’s 2011 construction. In 2020, Disser, Friedmann, and Hopp [DFH 3,4] again contended that the least-entered rule was exponential. We show that their arguments contain multiple flaws. In other words, the worst-case behavior of the least-entered rule has not been established. Neither [F 7] nor [DFH 3,4] provides pathological linear programs that can be tested. Instead, the authors contend that their pathological linear programs are of the form “(P)” as shown on page 12 of [DFH 3]. The authors contend that “the constraints of (P) ensure that the probability of entering a vertex u is equal to the probability of exiting u.” In fact, we note that the authors’ constraints “(P)” are flawed in at least three ways: a) they require the probability of exiting u to exceed the probability of entering u, b) they require the probability of exiting some nodes to exceed 1, and c) they overlook flows from decision nodes to decision nodes.[1] At my request, in August of 2025, Disser, Friedmann, and Hopp provided me with their first ten purportedly pathological LPs and the graph of their first purportedly pathological Markov Decision Process (MDP1). It is shown that: a) their first two pathological LPs are infeasible if the variables are supposed to be probabilities, as the authors contend, and b) their first purportedly pathological LP does not match up with their first purportedly pathological MDP. In other words, the authors have not come close to providing counterexamples to the “least-entered” rule.
References
Avis, D., Chvatal, V.: Notes on Bland’s pivoting rule. In: Polyhedral Combinatorics:
Dedicated to the memory of D.R. Fulkerson, pp 24-34. Springer, Heidelberg (1978)
Avis, D. Friedmann, O.: An exponential lower bound for Cunningham’s rule. Math. Program.
(1) 271-305 (2017)
Disser, Y., Friedmann, O., Hopp, A.V.: An exponential lower bound for Zadeh’s pivot rule (2020).
Full version. Available at https://arxiv.org/pdf/1911.01074.pdf
Disser, Y., Friedmann, O., Hopp, A.V.: An exponential lower bound for Zadeh’s pivot rule (2023). Mathematical Programming. 199:865-936
Disser, Y., Hopp, A.V. On Friedmann’s Subexponential Lower Bound for Zadeh’s Pivot Rule, Springer Nature Switzerland AG 2019, A. Lodi and V. Nagarajan (Eds), LNCS 11480, pp. 168-180, 2019.
Fathi, Computational complexity of LCPs associated with positive definite symmetric matrices, Math. Programming 17 (1979), no. 3, 335-344.
Friedmann, O.: A subexponential lower bound for Zadeh’s pivoting rule for solving linear programs and games. In: Proceedings of the 15th International Conference on Integer Programming and Combinatorial Optimization (IPCO), pp. 192-206 (2011).
Friedmann, O., Hansen, T.D., and Zwick, U. Subexponential lower bounds for the randomized pivoting rules for the simplex algorithm. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), pages 283-292, 2011.
Goldfarb, D. and Sit, W., Worst case behavior of the steepest edge simplex method,
Discrete Appl. Math. 1 (1979), 277-285.
Jeroslow, R. The simplex algorithm with the pivot rule of maximizing criterion improvement, Discrete Math. 4 (1979), 277-285.
Klee, V., Minty, G.J.: How good is the simplex algorithm? In: Inequalities III, pp. 159-175.
Academic Press, New York (1972)
Murty, K.G., Computational complexity of complementary pivot methods. Math.
Programming 15 (1978), no 3, 352-354.
Zadeh, N. A bad network problem for the simplex method and other minimum cost flow algorithms, Math. Programming 5 (1973) 255-266.
Zadeh, N. What is the worst case behavior of the simplex algorithm? Technical report 27, Department of Operations Research, Stanford, 1980
Downloads
Published
Issue
Section
License
Copyright (c) 2025 Norman Zada (Author)
This work is licensed under a Creative Commons Attribution 4.0 International License.
You are free to:
- Share — copy and redistribute the material in any medium or format for any purpose, even commercially.
- Adapt — remix, transform, and build upon the material for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
Under the following terms:
- Attribution — You must give appropriate credit , provide a link to the license, and indicate if changes were made . You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
Notices:
You do not have to comply with the license for elements of the material in the public domain or where your use is permitted by an applicable exception or limitation .
No warranties are given. The license may not give you all of the permissions necessary for your intended use. For example, other rights such as publicity, privacy, or moral rights may limit how you use the material.
