A subexponential randomized simplex algorithm (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A subexponential randomized simplex algorithm (extended abstract)

Full text

Pdf (811 KB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-fourth annual ACM symposium on Theory of computing table of contents

Victoria, British Columbia, Canada

Pages: 475 - 482

Year of Publication: 1992

ISBN:0-89791-511-9

Author

Gil Kalai

Institute of Mathematics, Hebrew University of Jerusalem, Jerusalem, Israel

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 14, Downloads (12 Months): 59, Citation Count: 31

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/129712.129759 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. Bj/Srner, M. Las Vergnas, B. Sturmfels, N. White and G. M. Ziegler, Oriented Matroids, Cambridge University Press, 1992, to appear.
	2	R. G. Bland, New finite pivoting rules for the simplex method, Math. of Op. Res. 2(1977), 103- 107.
	3	K. H. Borgwardt, The Simplex Method, a Probabilistic Analysis, Algorithms and Combinatorics I, Springer-Verlag, Berlin, 1987.
	4	V. Chv#ital, Linear Programming, W. H. Freeman, San Francisco, 1983.
	5	K L Clarkson, Linear programming in O(n × 3d2) time, Information Processing Letters, v.22 n.1, p.21-24, January 2, 1986 [doi>10.1016/0020-0190(86)90037-2]
	6	K. L. Clarkson, A las Vegas Algorithm for linear programming when the dimension is small, Proceedings STOC 1988, 452-456.
	7	G. B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, in" Activity Analysis of Production and Allocation, T. C. Koopman (Ed.) Cowles Commission Monograph 13, Wiley, New York, 1951, 339-347.
	8	G. B. Dantzig, Linear Programming and Extensions, Princeton University Press, Princeton, N.J., 1963.
	9	M E Dyer, On a multidimensional search technique and its application to the Euclidean one centre problem, SIAM Journal on Computing, v.15 n.3, p.725-738, August 1986 [doi>10.1137/0215052]
	10	M. E. Dyer and A. Frieze, random walks, totally unimodular matrices and a randomized dual simplex algorithm, 1992, to appear.
	11	D. Gale, How to solve linear inequalities, Amer. Math. Monthly 76(1969),589-599.
	12	J. E. Goodman and R. Pollack, Upper bounds for configurations and points in Rd, Discrete and Comp. Geometry, 1(1986), 219-227.
	13	B. Griinbaum, Convex Polytopes Ch. 16, Wiley Interscience, London, 1967.
	14	G. Kalai, The diameter problem for convex polytopes and f-vector theory, in: The Victor Klee Festschrift (P. Gritzman and B. Sturmfels, eds.), pp. 387-411, Amer. Math. Society, Providence, 1991.
	15	G. Kalai, Upper bounds for the diameter of graphs of convex polytopes, Discrete Comp. Geometry 7(1992), to appear.
	16	G. Kalai and D. J. Kleitman, A quasi-polynomial bound for diameter of graphs of polyhedra, Bull. Amer. Math Soc., 24 (Apr. 1992), in press.
	17	N. Karmarkar, A new polynomial-time algorithm for linear programming, Combinatorica, v.4 n.4, p.373-395, Dec. 1984 [doi>10.1007/BF02579150]
	18	L. G. Khachiyan, A polynomial algorithm in linear programming, Soviet Math. Doklady, 20 (1979), 191-194.
	19	V. Klee, Convex polyhedra and mathematics} programming, Proc. 1974 Int. Congress math. Vancouver, 51-56.
	20	Victor Klee , Peter Kleinschmidt, The d-step conjecture and its relatives, Mathematics of Operations Research, v.12 n.4, p.718-755, Nov. 1987 [doi>10.1287/moor.12.4.718]
	21	V. Klee and G.J. Minty, How good is the simplex algorithm, in: Inequalities Ill, pp. , O. Shisha (ed.) Academic Press, New-York ,1972, pp. 159- 175.
	22	V. Klee and D. Walkup, The d-step conjecture for polyhedra of dimension d < 6, Acta Math., 133, 53-78.
	23	D. G. Larman, Paths on polytopes, Proc. Lon. Math. Soc. 20(1970), 161-178.
	24	Jiří Matoušek , Micha Sharir , Emo Welzl, A subexponential bound for linear programming, Proceedings of the eighth annual symposium on Computational geometry, p.1-8, June 10-12, 1992, Berlin, Germany [doi>10.1145/142675.142678]
	25	P. McMullen, The maximal number of faces of a convex polytope, Mathematika 17(1970), 179- 184.
	26	N. Megiddo, Toward a genuinely polynomial algorithm for linear programming, SIAM J. Comp. 12(1983), 347-353.
	27	Nimrod Megiddo, Linear Programming in Linear Time When the Dimension Is Fixed, Journal of the ACM (JACM), v.31 n.1, p.114-127, Jan. 1984 [doi>10.1145/2422.322418]
	28	Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
	29	Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
	30	Micha Sharir , Emo Welzl, A Combinatorial Bound for Linear Programming and Related Problems, Proceedings of the 9th Annual Symposium on Theoretical Aspects of Computer Science, p.569-579, February 13-15, 1992
	31	Eva Tardos, A strongly polynomial algorithm to solve combinatorial linear programs, Operations Research, v.34 n.2, p.250-256, March-April 1986 [doi>10.1287/opre.34.2.250]

CITED BY 31

	Bernard Chazelle , Jiří Matoušek, On linear-time deterministic algorithms for optimization problems in fixed dimension, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.281-290, January 25-27, 1993, Austin, Texas, United States
	M. Pellegrini, Randomizing combinatorial algorithms for linear programming when the dimension is moderately high, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.101-108, January 07-09, 2001, Washington, D.C., United States
	Bernd Gärtner , József Solymosi , Falk Tschirschnitz , Emo Welzl , Pavel Valtr, One line and &egr;, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.306-315, July 2001, Hersonissos, Greece
	Jiří Matoušek, On geometric optimization with few violated constraints, Proceedings of the tenth annual symposium on Computational geometry, p.312-321, June 06-08, 1994, Stony Brook, New York, United States
	Rajiv Gupta , Scott A. Smolka , Shaji Bhaskar, On randomization in sequential and distributed algorithms, ACM Computing Surveys (CSUR), v.26 n.1, p.7-86, March 1994
	Michael T. Goodrich, Fixed-dimensional parallel linear programming via relative &egr;-approximations, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.132-141, January 28-30, 1996, Atlanta, Georgia, United States
	Jiří Matoušek , Micha Sharir , Emo Welzl, A subexponential bound for linear programming, Proceedings of the eighth annual symposium on Computational geometry, p.1-8, June 10-12, 1992, Berlin, Germany
	Edgar A. Ramos, Linear programming queries revisited, Proceedings of the sixteenth annual symposium on Computational geometry, p.176-181, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Bernd Gärtner , Emo Welzl, Explicit and implicit enforcing: randomized optimization, Computational Discrete Mathematics: advanced lectures, Springer-Verlag New York, Inc., New York, NY, 2001
	Bernard Chazelle, Computational geometry: a retrospective, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.75-94, May 23-25, 1994, Montreal, Quebec, Canada
	Sandeep Sen, Parallel multidimensional search using approximation algorithms: with applications to linear-programming and related problems, Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures, p.251-260, June 24-26, 1996, Padua, Italy
	Michael Saks, Kleitman and combinatorics, Discrete Mathematics, v.257 n.2-3, p.225-247, 28 November
	Bernd Gärtner, The random facet simplex algorithm on combinatorial cubes, Random Structures & Algorithms, v.20 n.3, p.353-381, May 2002
	Bernd Gärtner , Falk Tschirschnitz , Emo Welzl , József Solymosi , Pavel Valtr, One line and n points, Random Structures & Algorithms, v.23 n.4, p.453-471, December 2003
	Daniel Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.296-305, July 2001, Hersonissos, Greece
	Kenneth L. Clarkson, Las Vegas algorithms for linear and integer programming when the dimension is small, Journal of the ACM (JACM), v.42 n.2, p.488-499, March 1995
	Daniel A. Spielman , Shang-Hua Teng, Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time, Journal of the ACM (JACM), v.51 n.3, p.385-463, May 2004
	Viktor Petersson , Sergei Vorobyov, A randomized subexponential algorithm for parity games, Nordic Journal of Computing, v.8 n.3, p.324-345, Fall 2001
	Yana Kortsarts , Jeffrey Rufinus, How (and why) to introduce Monte Carlo randomized algorithms into a basic algorithms course?, Journal of Computing Sciences in Colleges, v.21 n.2, p.195-203, December 2005
	Yana Kortsarts , Jeffrey Rufinus, Teaching the power of randomization using a simple game, ACM SIGCSE Bulletin, v.38 n.1, March 2006
	Marcin Jurdziński , Mike Paterson , Uri Zwick, A deterministic subexponential algorithm for solving parity games, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.117-123, January 22-26, 2006, Miami, Florida
	Bernd Gärtner , Ingo Schurr, Linear programming and unique sink orientations, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.749-757, January 22-26, 2006, Miami, Florida
	Henrik Björklund , Sergei Vorobyov, Combinatorial structure and randomized subexponential algorithms for infinite games, Theoretical Computer Science, v.349 n.3, p.347-360, 16 December 2005
	Henrik Björklund , Sergei Vorobyov, A combinatorial strongly subexponential strategy improvement algorithm for mean payoff games, Discrete Applied Mathematics, v.155 n.2, p.210-229, January, 2007
	Valentin E. Brimkov , Stefan Dantchev, Digital hyperplane recognition in arbitrary fixed dimension within an algebraic computation model, Image and Vision Computing, v.25 n.10, p.1631-1643, October, 2007
	B. Gärtner , J. Matoušek , L. Rüst , P. Škovroň, Violator spaces: Structure and algorithms, Discrete Applied Mathematics, v.156 n.11, p.2124-2141, June, 2008
	Sergei Vorobyov, Cyclic games and linear programming, Discrete Applied Mathematics, v.156 n.11, p.2195-2231, June, 2008
	Michael Goldwasser, A survey of linear programming in randomized subexponential time, ACM SIGACT News, v.26 n.2, p.96-104, June 1995
	Marc van Kreveld , Rodrigo I. Silveira, Embedding rivers in polyhedral terrains, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Friedrich Eisenbrand , Nicolai Hähnle , Thomas Rothvoß, Diameter of polyhedra: limits of abstraction, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark