One line and n points
作者： Bernd Gärtner , Falk Tschirschnitz , Emo Welzl , József Solymosi , Pavel Valtr
DOI: 10.1002/RSA.10099
关键词:
摘要: We analyze a randomized pivoting process involving one line and n points in the plane. The models behavior of RANDOM-EDGE simplex algorithm on simple polytopes with facets dimension - 2. obtain tight O(log2 n) bound for expected number pivot steps. This is first nontrivial RANDOM-EDGE, which goes beyond bounds specific polytopes. itself can be interpreted as certain 2-variable linear programming problems, we prove Θ(n) its runtime.
core.ac.uk
sci-hub.se 参考文章(14)
Combinatorics with a Geometric Flavor Birkhäuser Basel. pp. 742- 791 ,(2000) , 10.1007/978-3-0346-0425-3_7
Pavel Valtr, Falk Tschirschnitz, Bernd Gärtner, József Solymosi, Emo Welzl, One line and n points. symposium on the theory of computing. pp. 306- 315 ,(2001)
Falk Tschirschnitz, LP-related Properties of Polytopes with Few Facets ETH. ,(2003) , 10.3929/ETHZ-A-004624080
Gil Kalai, Linear programming, the simplex algorithm and simple polytopes Mathematical Programming. ,vol. 79, pp. 217- 233 ,(1997) , 10.1007/BF02614318
Gil Kalai, A subexponential randomized simplex algorithm (extended abstract) symposium on the theory of computing. pp. 475- 482 ,(1992) , 10.1145/129712.129759
Oren Patashnik, Donald E. Knuth, Ronald L. Graham, Concrete Mathematics: A Foundation for Computer Science ,(1994)
E. Welzl, Entering and leaving j-facets Discrete and Computational Geometry. ,vol. 25, pp. 351- 364 ,(2001) , 10.1007/S004540010085
Bernd Gärtner, József Solymosi, Falk Tschirschnitz, Emo Welzl, Pavel Valtr, One line and ε Proceedings of the thirty-third annual ACM symposium on Theory of computing - STOC '01. pp. 306- 315 ,(2001) , 10.1145/380752.380814
Kenneth Steiglitz, Christos H. Papadimitriou, Combinatorial Optimization: Algorithms and Complexity ,(1981)
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