LINEAR-PROGRAMMING, THE SIMPLEX ALGORITHM AND SIMPLE POLYTOPES

Authors
KALAI G
Citation
G. Kalai, LINEAR-PROGRAMMING, THE SIMPLEX ALGORITHM AND SIMPLE POLYTOPES, Mathematical programming, 79(1-3), 1997, pp. 217-233
Citations number
32
Categorie Soggetti
Operatione Research & Management Science",Mathematics,"Operatione Research & Management Science",Mathematics,"Computer Science Software Graphycs Programming
Journal title
Mathematical programming → ACNP
ISSN journal
00255610
Volume
79
Issue
1-3
Year of publication
1997
Pages
217 - 233
Database
ISI
SICI code
0025-5610(1997)79:1-3<217:LTSAAS>2.0.ZU;2-X
Abstract
In the first part of the paper we survey some far-reaching application s of the basic facts of linear programming to the combinatorial theory of simple polytopes. In the second part we discuss some recent develo pments concerning the simplex algorithm. We describe subexponential ra ndomized pivot rules and upper bounds on the diameter of graphs of pol ytopes. (C) 1997 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.