The criss-cross method can take Ω(nd) pivots

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The criss-cross method can take Ω(n^d) pivots

Full text

Pdf (257 KB)

Source

Annual Symposium on Computational Geometry archive
Proceedings of the twentieth annual symposium on Computational geometry table of contents

Brooklyn, New York, USA

SESSION: Session 11 table of contents

Pages: 401 - 408

Year of Publication: 2004

ISBN:1-58113-885-7

Authors

Bohdan Kaluzny	McGill University, Montreal, Canada
Komei Fukuda	ETH Zentrum, Zurich, Switzerland

Sponsors

ACM: Association for Computing Machinery
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 10, Downloads (12 Months): 25, Citation Count: 0

Additional Information:

abstract references 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/997817.997877 What is a DOI?

ABSTRACT

Using deformed products of arrangements, we construct a family of linearprograms with n inequalities in R^d on which, in the worst-case, the least-index criss-cross methodrequires Ω(n^d) (for fixed d) pivots to reach optimality.

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	N. Amenta and G. Ziegler. Deformed products and maximal shadows of polytopes. Contemporary Mathematics 223: 57--90, 1999.
	2	D. Avis and V. Chvatal, Notes on Bland's rule. Mathematical Programming Study 8: 24--34, 1978.
	3	K. Fukuda and T. Matsui. On the finiteness of the criss-cross method. European Journal of Operations Research 52: 119--124, 1991.
	4	K. Fukuda and T. Terlaky. On the existence of a short admissible pivot sequence for feasibility and linear optimization problems. Pure Mathematics and Applications, Mathematics of Optimization 10(4): 431--447, 2000.
	5	V. Klee and G.J. Minty. How good is the simplex algorithm? In O. Shisha, editor, Inequalities-III pages 159--175. Academic Press, New York, 1972.
	6	P. McMullen. The maximum number of faces of a convex polytope. Mathematika 17: 179--184, 1970.
	7	Jürgen Richter-Gebert , Günter M. Ziegler, Oriented matroids, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
	8	C. Roos, An exponential example for Terlaky's pivoting rule for the criss-cross simplex method, Mathematical Programming: Series A and B, v.46 n.1, p.79-84, Jan. 1990 [doi>10.1007/BF01585729]
	9	T. Terlaky. A convergent criss-cross method. Math. Oper. und Stat. ser. Optimization 16(5): 683--690, 1985.
	10	Z. Wang. A conformal elimination free algorithm for oriented matroid programming. Chinese Annals of Mathematics 8(B1), 1987.
	11	T. Zaslavsky. Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Mem. Amer. Math. Soc.1 (No 154 MR 50), 1975.
	12	S. Zionts. The criss-cross method for solving linear programming problems. Management Science 15(7): 426--445, 1969.