The Random Edge Simplex Algorithm on Dual Cyclic 4-Polytopes
作者： Rafael Gillmann
DOI:
关键词: Edge (geometry) 、 Combinatorics 、 Contrast (statistics) 、 Realization (systems) 、 Omega 、 Simplex algorithm 、 Facet (geometry) 、 Polytope 、 Dual (category theory) 、 Mathematics
摘要: The simplex algorithm using the random edge pivot-rule on any realization of a dual cyclic 4-polytope with n facets does not take more than O(n) pivot-steps. This even holds for general abstract objective functions (AOF) / acyclic unique sink orientations (AUSO). methods can be used to show analogous results products two polygons. In contrast, we that facet is slow 4-polytopes, i.e. there are AUSOs which takes at least \Omega(n^2) steps.
harvard.edu参考文章(19)
Jonathan A. Kelner, Daniel A. Spielman, A Randomized Polynomial-Time Simplex Algorithm for Linear Programming (Preliminary Version) Electronic Colloquium on Computational Complexity. ,(2005)
Haase, Ziegler, Examples and Counterexamples for the Perles Conjecture Discrete and Computational Geometry. ,vol. 28, pp. 29- 44 ,(2002) , 10.1007/S00454-001-0085-0
Günter M. Ziegler, Lectures on Polytopes ,(1994)
Micha Sharir, Emo Welzl, A combinatorial bound for linear programming and related problems STACS 92. pp. 567- 579 ,(1992) , 10.1007/3-540-55210-3_213
L.G. Khachiyan, Polynomial algorithms in linear programming USSR Computational Mathematics and Mathematical Physics. ,vol. 20, pp. 53- 72 ,(1980) , 10.1016/0041-5553(80)90061-0
Daniel A. Spielman, Shang-Hua Teng, Smoothed analysis of algorithms Journal of the ACM. ,vol. 51, pp. 385- 463 ,(2004) , 10.1145/990308.990310
Volker Kaibel, Rafael Mechtel, Micha Sharir, Günter M. Ziegler, The Simplex Algorithm in Dimension Three SIAM Journal on Computing. ,vol. 34, pp. 475- 497 ,(2005) , 10.1137/S0097539703434978
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
Andrei Z. Broder, Martin E. Dyer, Alan M. Frieze, Prabhakar Raghavan, Eli Upfal, The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height Information Processing Letters. ,vol. 56, pp. 79- 81 ,(1995) , 10.1016/0020-0190(95)00101-H
Jiří Matoušek, Lower bounds for a subexponential optimization algorithm Random Structures and Algorithms. ,vol. 5, pp. 591- 607 ,(1994) , 10.1002/RSA.3240050408