A subexponential randomized simplex algorithm (extended abstract)
A subexponential randomized simplex algorithm (extended abstract)
复制标题
次指数随机单纯形算法（扩展摘要）
DOI：
--
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
G. Kalai
中科院分区：
文献类型：
--
作者：
G. Kalai
我们描述了单纯形算法的一个随机变体。对于每个具有d个变量和n个约束的线性规划问题，我们的算法所要求的算术运算的期望次数最多为{n C.-, ~2Cwd&d}。（C是绝对常数。）
We describe a randomized variant of the simplex algcrrithm. The expected number of arithmetic operations required by our algorithm for every linear programming problem wit h d variables and n constraints is at most min{n C.-, ~2Cwd&d }. (C is an absolute constant.)