Random edge can be exponential on abstract cubes
Random edge can be exponential on abstract cubes
复制标题
DOI：
10.1109/focs.2004.56
复制
发表时间：
2004-10
期刊：
影响因子：
--
通讯作者：
J. Matoušek;Tibor Szabó
中科院分区：
文献类型：
--
作者：
J. Matoušek;Tibor Szabó
我们证明了随机边，总是选择一个随机的改进边进行的单纯形算法，可以采取一个温和的指数级的步骤，在模型的抽象目标函数（K。W. Hoke（1998）和G. Kalai（1988）以不同的名字）。我们定义了一个抽象的目标函数的n维立方体的算法，开始于一个随机的顶点，需要至少exp（const /spl middot/ n/sup 1/3/）步骤的概率很高。最好的前下限是二次的。因此，为了在多项式时间内实现随机边缘，几何学必须有所帮助。
We prove that random edge, the simplex algorithm that always chooses a random improving edge to proceed on, can take a mildly exponential number of steps in the model of abstract objective functions (introduced by K. W. Hoke (1998) and by G. Kalai (1988) under different names). We define an abstract objective function on the n-dimensional cube for which the algorithm, started at a random vertex, needs at least exp(const /spl middot/ n/sup 1/3/) steps with high probability. The best previous lower bound was quadratic. So in order for random edge to succeed in polynomial time, geometry must help.