论文标题
线性程序的强烈多项式时间单纯算法的存在
The existence of a strongly polynomial time simplex algorithm for linear programs
论文作者
论文摘要
众所周知，优化和离散几何形状中最具挑战性的问题是线性程序（LPS）是否有强烈的多项式时间单纯算法。本文通过使用美国提出的参数分析技术对这个问题提供了积极的答案（ARXIV：2006.08104）。我们表明，有一种单纯形算法，其旋转步骤的数量不超过LP问题的变量数量。
It is well known that the most challenging question in optimization and discrete geometry is whether there is a strongly polynomial time simplex algorithm for linear programs (LPs). This paper gives a positive answer to this question by using the parameter analysis technique presented by us (arXiv:2006.08104). We show that there is a simplex algorithm whose number of pivoting steps does not exceed the number of variables of a LP problem.
