Linear Programming, the Simplex Algorithm and Simple Polytopes

Subject Areas : linear Programming

Das Bhusan ¹ , Biswal Bagaban ² , J.P Tripathy ³

1 - Department of Mathematics,Balasor college of Engg & Teach. Sergarh, Balasore, Orissa, India
2 - Department of Mathematics F.M.Autonomous College, Balasore, Orissa, India
3 - Department of Mathematics Gurukul Institute of Bhubaneswar,Orissa,India

Received: 2010-07-30 Accepted : 2010-08-30 Published : 2010-09-01

Keywords: simplex algorithm, Randomized Pivot rule complexity combinational theory of simple polytopes,

Abstract :

In the first part of the paper we survey some far reaching applications of the basis facts of linear programming to the combinatorial theory of simple polytopes. In the second part we discuss some recent developments concurring the simplex algorithm. We describe sub-exponential randomized pivot roles and upper bounds on the diameter of graphs of polytopes.

References:

[1] Amenta N., and Ziegler G., Deformed products and maximal shadows preprint 502,1996, TU Berlin to appear.

[2] Billera L.J., and Lee C. W., A proof of sufficiency of Mac muller’s conditions for f-vectors of simplified convex polytopes J. Combes Theory, series 31, 237 – 255, 1981.

[3] Blind R., and mani P., on Puzzles and polytopes isomorphism, Ae-quations math 34,287 -297, 1987.

[4] Borgwardt K.H., The simplex method A probabilities Analysis Algorithms and combinations Vol – I (Springer, Berlies 1987)

[5] ciarkson K.L., A Lasveges Algorithm for linear Programming when the dimensional is small, J ACM, 42(2),488 -499, 1995.

[6] Dantzig G.B., linear programming and extensions (Princeton University Press, Princelon NJ 1963.

[7] Dyer M.E., and A Frieze Random walks totally Modular Matrices and a randomized dual simplex algorithm Mathematical programming, 64, 1-16, 1994.

[8] Gartner B., A sub exponential algorithm for abstract optimization problems SIAM J. Compute, 24 ,1018 -1035, 1995.

[9] Gantner B., Henk M., and Ziegler G., Randomized simplex algorithms on Klee- Minty cubes to appear.

[10] Grunbaum B., convex prlytoes (Inter science Londaon 1967)

[11] Holt F., and Klee V., Many Dolytopes Meeting the conjectured Hirsch bound (1997), to appear.

[12] Khachiyan L.G., A Dolynomial Algorithm in LP soujet math, Doklady 20 191-194, 1979.

[13] Kalai G., A simple way to tell a simple polytope forms its graph, J. Combine, Theory series A 49, 381 – 383, 1988.

[14] Kalai G., The diameter of graphs of convex polytopes and f- vector theory in Applied Geometry and Discreate mathematics, The Klee Festschrifts, DIMACS Series in discrete mathematics and computer science Vol-4, 387 -411, 1941.

[15] Kalai G., upper bounds for the diameter of graphs of convex plywpes discreet computational geometry, 8, 363 – 372, 1992.

[16] Kalai G., A sub exponential randomized simplex algorithm in Preceding of the 24^th Annual ACM symposium on the Theory of computing (ACM Press Victoria 1992), 475 – 482.

[17] Kalai G., and Kleitman D.J., A quasi – Polynomial bound for diameter of graphs of polyhedral, Bull Amer Muth Soc, 26, 315 -316, 1992.

[18] Klee V., and Minty G.J., How good is simplex algorithm is o shisha, ed inequalities III (Academic press, New Youk, 315-316, 1972.

[19] Kle V., and walkup D., the d step connective for polyhedral of dimension d < 6 Acts math, 133, PP S3 -78.

[20] Lanma D.G., paths on polytopes, proc London math SOC, 20, 161 – 178, 1970.

[21] Matousek J., Lower bounds for a sub exponential optimization algorithm Random structures and algorithms, 5, 591 – 607, 1994.

[22] Matousek J., Msharir and Welzel E., A sub exponential bound for LP in Proceeding of the 8^th Annual symposium on computational Geometry, 1-8, 1992.

[23] McMullen P., The maximal number of faces of a convex polypes, mathematical, 17, 179 – 184, 1970.

[24] Mullen P. Mc., on simple polytpes, Inver Math, 113, 419 – 444, 1993.

[25] Megiddo N., LP in linear time when the dimension is fixed J ACM, 31, 114 – 127, 1984.

[26] Mulmuley K., computational geometry, An introduction through Randomized Algorithm (Prentice – Hall, Englewood liffs NT 1994).

[27] sharir M., and Welzel E., A combinational bound for LP and related problems proceedings of the 9^th symposium on theoretical aspect of computer science letter Notes in computer science, Vol 577, Springer, Berlies , 569-579, 1992.

 

[28] Slidel R., Small – Dimensional LP and convex nulls made easy, discreate computational geometry, 6, 423 -434, 1991.

[29] Schrijver A., Theory of linear and integer programming (Wiley –intense, New Yourk 1980.

[30] Stanly R., the number of faces of simplified convex poltpes it adv math, 35,236-23, 1980.

[31] Tandos E., A strongly polynomial algorithm to solve combinational linear programs, operation research, 34, 250 – 256, 1986.

[32] Ziegler GM., Lichens on polytopes, Gnaduat Texts Mathematics Vol. 152 (Springer, New Your, 1995)