A Subexponential Lower Bound for Zadeh's Pivoting Rule for Solving Linear Programs and Games
A Subexponential Lower Bound for Zadeh's Pivoting Rule for Solving Linear Programs and Games
复制标题
DOI：
10.1007/978-3-642-20807-2_16
复制
发表时间：
2011-06
期刊：
影响因子：
--
通讯作者：
Oliver Friedmann
中科院分区：
文献类型：
--
作者：
Oliver Friedmann
单纯形算法是实际中求解线性规划最常用的算法之一。然而，大多数旋转规则都需要指数数量的步骤来解决一些线性规划。在此之前，Zadeh旋转法则[25]的非多项式下界是未知的。Zadeh旋转法则也称为最少输入法则，属于记忆改进法则家族，它从当前基本可行解（或顶点）的所有改进旋转步骤中选择一个最少输入的步骤。我们提供了第一次指数（即，我们的下界是通过利用单纯形算法执行的旋转步骤之间的联系和改进策略迭代算法执行的开关来获得的。我们首先建立2-playerparity游戏（PG）上的政策迭代theLeast-Entered，规则执行一个次指数数量的迭代。然后，我们将奇偶校验游戏转化为1-playerMarkov决策过程（MDP），它几乎立即对应于具体的线性规划。
Thesimplexalgorithm is among the most widely used algorithms for solvinglinear programsin practice. Most pivoting rules are known, however, to need an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior to this work, forZadeh’spivoting rule [25].Also known as theLeast-Entered, rule, Zadeh’s pivoting method belongs to the family of memorizing improvement rules, which among all improving pivoting steps from the current basic feasible solution (orvertex) chooses one which has been entered least often. We provide the firstsubexponential(i.e., of the form) lower bound for this rule.Our lower bound is obtained by utilizing connections between pivoting steps performed by simplex-based algorithms andimproving switchesperformed bypolicy iterationalgorithms for 1-player and 2-player games. We start by building 2-playerparity games(PGs) on which the policy iteration with theLeast-Entered, rule performs a subexponential number of iterations. We then transform the parity games into 1-playerMarkov Decision Processes(MDPs) which corresponds almost immediately to concrete linear programs.