摘要: We construct a class of abstract objective functions on the cube, such that algorithm BottomAntipodal takes exponentially many steps to find maximum. A similar is constructed for process BottomTop, also requiring steps.
springer.com
sci-hub.se 参考文章(15)
Donald Goldfarb, On the Complexity of the Simplex Method Springer, Dordrecht. pp. 25- 38 ,(1994) , 10.1007/978-94-015-8330-5_2
George J. Minty, Victor Klee, HOW GOOD IS THE SIMPLEX ALGORITHM Inequalities. pp. 159- 175 ,(1970)
Ilan Adler, George B. Dantzig, Maximum diameter of abstract polytopes Pivoting and Extension. pp. 20- 40 ,(1974) , 10.1007/BFB0121238
Ingo Schurr, Tibor Szabó, Finding the Sink Takes Some Time european symposium on algorithms. pp. 833- 844 ,(2002) , 10.1007/3-540-45749-6_72
Ingo Schurr, Bernd Gärtner, Linear programming and unique sink orientations symposium on discrete algorithms. pp. 749- 757 ,(2006) , 10.5555/1109557.1109639
I. Adler, R. Saigal, Long Monotone Paths in Abstract Polytopes Mathematics of Operations Research. ,vol. 1, pp. 89- 95 ,(1976) , 10.1287/MOOR.1.1.89
Walter D. Morris jr., Randomized pivot algorithms for P-matrix linear complementarity problems Mathematical Programming. ,vol. 92, pp. 285- 296 ,(2002) , 10.1007/S101070100268
Gil Kalai, A subexponential randomized simplex algorithm (extended abstract) symposium on the theory of computing. pp. 475- 482 ,(1992) , 10.1145/129712.129759
Nina Amenta, Günter M. Ziegler, Shadows and slices of polytopes symposium on computational geometry. pp. 10- 19 ,(1996) , 10.1145/237218.237228
Kathy Williamson Hoke, Completely unimodal numberings of a simple polytope Discrete Applied Mathematics. ,vol. 20, pp. 69- 81 ,(1988) , 10.1016/0166-218X(88)90042-X