Linear programming, the simplex algorithm and simple polytopes
作者： Gil Kalai
DOI: 10.1007/BF02614318
关键词:
摘要: In the first part of paper we survey some far-reaching applications basic facts linear programming to combinatorial theory simple polytopes. second discuss recent developments concerning simplex algorithm. We describe subexponential randomized pivot rules and upper bounds on diameter graphs © 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
springer.com
sci-hub.se 参考文章(33)
George J. Minty, Victor Klee, HOW GOOD IS THE SIMPLEX ALGORITHM Inequalities. pp. 159- 175 ,(1970)
Karl Heinz Borgwardt, The Simplex Method: A Probabilistic Analysis ,(1986)
Ketan Mulmuley, Computational geometry : an introduction through randomized algorithms Prentice-Hall. ,(1994)
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
Alexander Schrijver, Theory of Linear and Integer Programming ,(1986)
Victor Klee, David W. Walkup, The d-step conjecture for polyhedra of dimension d<6 Acta Mathematica. ,vol. 117, pp. 53- 78 ,(1967) , 10.1007/BF02395040
Jiří Matoušek, Micha Sharir, Emo Welzl, A subexponential bound for linear programming symposium on computational geometry. pp. 1- 8 ,(1992) , 10.1145/142675.142678
Roswitha Blind, Peter Mani-Levitska, Puzzles and polytope isomorphisms. Aequationes Mathematicae. ,vol. 34, pp. 287- 297 ,(1987) , 10.1007/BF01830678
Kenneth L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small Journal of the ACM. ,vol. 42, pp. 488- 499 ,(1995) , 10.1145/201019.201036