论文标题
在Facet Pivot单纯形方法上，用于线性编程II：线性迭代绑定
On the facet pivot simplex method for linear programming II: a linear iteration bound
论文作者
论文摘要
Hirsch的猜想指出，与n个方面的任何$ d $二维多层人物的直径最多等于$ n -d $。桑托斯（Santos）反驳了这一猜想（对赫希（Hirsch）猜想的反例，数学年鉴，172（1）383-412，2012）。桑托斯（Santos）工作的含义是，所有{\ it vertex}枢轴算法无法在最坏的情况下解决$ n -d $ dertex Pivot Itererations中的线性编程问题。 在这一系列论文的第一部分中，我们提出了一个{\ it facet}枢轴方法。在本文中，我们表明，在最坏的情况下，在最坏的情况下，提出的Facet Pivot方法可以解决规范的线性编程问题。这项工作的灵感来自Smale的问题9（下个世纪的数学问题，在Arnold，V。I。; Atiyah，M。; Lax，P。; Mazur，B。数学：前沿和观点，美国数学学会，271-294，1999）。
The Hirsch Conjecture stated that any $d$-dimensional polytope with n facets has a diameter at most equal to $n - d$. This conjecture was disproved by Santos (A counterexample to the Hirsch Conjecture, Annals of Mathematics, 172(1) 383-412, 2012). The implication of Santos' work is that all {\it vertex} pivot algorithms cannot solve the linear programming problem in the worst case in $n - d$ vertex pivot iterations. In the first part of this series of papers, we proposed a {\it facet} pivot method. In this paper, we show that the proposed facet pivot method can solve the canonical linear programming problem in the worst case in at most $n-d$ facet pivot iterations. This work was inspired by Smale's Problem 9 (Mathematical problems for the next century, In Arnold, V. I.; Atiyah, M.; Lax, P.; Mazur, B. Mathematics: frontiers and perspectives, American Mathematical Society, 271-294, 1999).
