Linear programming with two variables per inequality in poly-log time
Linear programming with two variables per inequality in poly-log time
复制标题
在多对数时间内每个不等式有两个变量的线性规划
DOI：
--
复制
发表时间：
1986
期刊：
影响因子：
--
通讯作者：
V. Ramachandran
中科院分区：
文献类型：
--
作者：
G. S. Lueker;N. Megiddo;V. Ramachandran
讨论了每个不等式最多两个变量的线性规划问题的并行时间复杂度。设n和m分别表示线性规划问题中变量的数目和不等式的数目。假定所有的不平等都是弱的。在并发-读-独占-写PRAM模型下，给出了一种$O((log m + log^2 n) log^2 n)$ time的并行可行性判定算法。在最坏的情况下，它需要$mn^{O(log n)}$个处理器，尽管不知道这个界限是否严格。当问题可行时，可以在相同的复杂度内计算出解决方案。此外，目标函数中最多有两个非零系数的线性规划问题可以在相同数量的处理器上用多对数时间求解。因此，所有这些问题都可以用$O((log m + log ^2 n)^2 log ^2 n)$空间依次求解。(这些边界假设数字占用$O(1)$空间，对它们进行运算需要$O(1)$时间；p…
The parallel time complexity of the linear programming problem with at most two variables per inequality is discussed. Let n and m denote the number of variables and the number of inequalities, respectively, in a linear programming problem. It is assumed that all inequalities are weak. Under the concurrent-read-exclusive-write PRAM model, an $O((log m + log^2 n) log^2 n)$-time parallel algorithm for deciding feasibility is described. It requires $mn^{O(log n)}$ processors in the worst case, though it is not known whether this bound is tight. When the problem is feasible, a solution can be computed within the same complexity. Moreover, linear programming problems with at most two nonzero coefficients in the objective function can be solved in poly-log time on a similar number of processors. Consequently, all these problems can be solved sequentially with only $O((log m + log ^2 n)^2 log ^2 n)$ space. (These bounds assume that numbers take $O(1)$ space, and arithmetic on them takes $O(1)$ time; the p...