An exponential lower bound for Zadeh's pivot rule

• 成果类型: Article
• 署名作者: Disser, Yann; Friedmann, Oliver; Hopp, Alexander, V
• 署名单位: Technical University of Darmstadt; University of Munich; Merck KGaA
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-022-01848-x
• 发表日期: 2023
• 页码: 865-936
• 关键词: simplex; edge

摘要

The question whether the Simplex Algorithm admits an efficient pivot rule remains one of the most important open questions in discrete optimization. While many natural, deterministic pivot rules are known to yield exponential running times, the random-facet rule was shown to have a subexponential running time. For a long time, Zadeh's rule remained the most prominent candidate for the first deterministic pivot rule with subexponential running time. We present a lower bound construction that shows that Zadeh's rule is in fact exponential in the worst case. Our construction is based on a close relation to the Strategy Improvement Algorithm for Parity Games and the Policy Iteration Algorithm for Markov Decision Processes, and we also obtain exponential lower bounds for Zadeh's rule in these contexts.