Towards a Genuinely Polynomial Algorithm for Linear Programming
Towards a Genuinely Polynomial Algorithm for Linear Programming
复制标题
线性规划的真正多项式算法
DOI：
10.1137/0212022
复制
发表时间：
1983
期刊：
影响因子：
--
通讯作者：
N. Megiddo
中科院分区：
文献类型：
--
作者：
N. Megiddo
线性编程算法如果不超过$ p（m，n）$算术操作来解决订单$ m \ times n $的问题，则称为$ p（m，n）$算法，其中P是多项式。尚不清楚这种算法是否存在。我们提出了一种真正的多项式算法，该算法是解决线性不平等的更简单问题，每个不等式最多都有两个变量。所需的操作数为$ O（Mn^3 \ log {\ text {m}}）$。所使用的技术是在以前的论文中开发的，其中引入了新型的二进制搜索想法。
A linear programming algorithm is called genuinely polynomial if it requires no more than $p(m,n)$ arithmetic operations to solve problems of order $m \times n$, where p is a polynomial. It is not known whether such an algorithm exists. We present a genuinely polynomial algorithm for the simpler problem of solving linear inequalities with at most two variables per inequality. The number of operations required is $O(mn^3 \log {\text{m}})$. The technique used was developed in a previous paper where a novel binary search idea was introduced.