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:

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)