Title: Is Zadeh's Least-Entered Pivot Rule Exponential? Show Chinese title

Title: 扎德的最小进入单纯形法规则是指数级的吗？

Abstract: 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. 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. Show Chinese abstract

Abstract: 2011年，Friedmann [F 7] 声称证明了存在病态线性规划问题，对于这些问题，使用Zadeh最小进入规则的单纯形法 [Z 14] 将需要指数级的旋转次数。 2019年，Disser和Hopp [DH 5] 指出Friedmann在2011年的构造中存在错误。 2020年， Disser、Friedmann和Hopp [DFH 3,4] 再次主张最小进入规则是指数级的。 我们表明他们的论点包含多个缺陷。 换句话说，最小进入规则的最坏情况行为尚未被确立。 [F 7] 或 [DFH 3,4] 都没有提供可以测试的病态线性规划问题。 相反，作者主张他们的病态线性规划问题形式如[DFH 3]第12页所示的(P)。 作者主张(P)的约束确保了进入顶点u的概率等于退出u的概率。 事实上，我们注意到作者的约束(P)至少有三个方面的缺陷：a) 它们要求退出u的概率超过进入u的概率，b) 它们要求某些节点的退出概率超过1，c) 它们忽略了从决策节点到决策节点的流量。 在我要求下，2025年8月， Disser、Friedmann和Hopp 向我提供了他们前十个所谓的病态LP以及他们第一个所谓的病态马尔可夫决策过程（MDP1）的图。 结果显示：a) 如果变量应被视为概率（如作者所主张的），则他们的前两个病态LP是不可行的，b) 他们第一个所谓的病态LP与其第一个所谓的病态MDP不一致。 换句话说，作者尚未接近提供对最小进入规则的反例。