Linear Programming in Linear Time When the Dimension Is Fixed

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Linear Programming in Linear Time When the Dimension Is Fixed

Full text

Pdf (739 KB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 1 (January 1984) table of contents

Pages: 114 - 127

Year of Publication: 1984

ISSN:0004-5411

Author

Nimrod Megiddo

Computer-Science Department, Stanford University, Stanford, CA and Tel Aviv University, Tel-Aviv, Israel

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 98, Citation Count: 79

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/2422.322418 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	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	Jon Louis Bentley, Multidimensional divide-and-conquer, Communications of the ACM, v.23 n.4, p.214-229, April 1980 [doi>10.1145/358841.358850]
	3	DANIZIG, G.B. Linear Programming and Extensions Princeton University Press, Princeton, N.J., 1963.
	4	Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
	5	Robert W. Floyd , Ronald L. Rivest, Expected time bounds for selection, Communications of the ACM, v.18 n.3, p.165-172, March 1975 [doi>10.1145/360680.360691]
	6	GRUNBAUM, B. Convex Polytopes. Wiley, New York, 1967.
	7	KHACHIAN, L.G A polynomial algorithm in linear programming. Soviet Math. Dokl. 20 (1979), 191-194.
	8	KLEE, V., AND MINTY, G.J.How good is the simplex algorithm? In Inequalities, vol. 3. Academic Press, New York, 1972, pp. 159-175.
	9	KNUTH, D.E. MathemaUcal analysis of algorithms. In lnformatton Processing 71. Elsevier North- Holland, New York, 1972, pp. 19-27.
	10	MEGIDDO, N.Is binary encoding appropriate for the problem-language relationship? Theor. Comput. So 19 (1982), 337-341.
	11	MEGIDDO, N.Solving linear programming when the dimension is fixed. Dept. of Statistics, Tel Avlv Univemty, April 1982.
	12	MEGIDDO, N.Linear.time algonthms for linear programming in Rz and related problems. SIAM J Comput 12, 4 (Nov. 1983).
	13	MEGIDDO, N.Towards a genuinely polynomial algorithm for linear programming. SlAM J. Comput. 12, 2 (May 1983), 347-353.
	14	MEISEL, W.S. Computer-Oriented Approaches to Pattern Recognition. Academic Press, New York, 1972.
	15	MONIER, L.Combinatorial solutions of multidtmensional divide-and-conquer reeurre, nces. Z Algorithms 1 (I980), 60-74.
	16	RICE, J.The Apprommatlon of Functions. Vol. 1; The Linear Theory. Addison-Wesley, Reading, Mass., 1964.
	17	SCHONHAGE, A., PATERSON, M., AND PIPPENOER, N.Finding the median. J. Compm. Syst. SeL 13 (1976), 184-199.
	18	Michael Ian Shamos, Computational geometry., 1978
	19	SMALE, $. On the average speed of the simplex method of hnear programming. To appear in Math Program

CITED BY 79

	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
	Wolfgang Maass, Bounds for the computational power and learning complexity of analog neural nets, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.335-344, May 16-18, 1993, San Diego, California, United States
	Gil Kalai, A subexponential randomized simplex algorithm (extended abstract), Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.475-482, May 04-06, 1992, Victoria, British Columbia, Canada
	Seth Teller , Pat Hanrahan, Global visibility algorithms for illumination computations, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.239-246, September 1993
	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
	Timothy M. Chan, Output-sensitive results on convex hulls, extreme points, and related problems, Proceedings of the eleventh annual symposium on Computational geometry, p.10-19, June 05-07, 1995, Vancouver, British Columbia, Canada
	Carolyn Habit Norton , Serge A. Plotkin , Éva Tardos, Using separation algorithms in fixed dimension, Proceedings of the first annual ACM-SIAM symposium on Discrete algorithms, p.377-387, January 22-24, 1990, San Francisco, California, United States
	Edith Cohen , Nimrod Megiddo, Strongly polynomial-time and NC algorithms for detecting cycles in periodic graphs, Journal of the ACM (JACM), v.40 n.4, p.791-830, Sept. 1993
	Michael T. Goodrich, Efficient piecewise-linear function approximation using the uniform metric: (preliminary version), Proceedings of the tenth annual symposium on Computational geometry, p.322-331, June 06-08, 1994, Stony Brook, New York, United States
	E. Cohen , N. Megiddo, Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.523-534, May 14-17, 1989, Seattle, Washington, United States
	Takeshi Tokuyama, Minimax parametric optimization problems and multi-dimensional parametric searching, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.75-83, July 2001, Hersonissos, Greece
	Nora H. Sleumer, Output-sensitive cell enumeration in hyperplane arrangements, Nordic Journal of Computing, v.6 n.2, p.137-147, Summer 1999
	Jiří Matoušek , Otfried Schwarzkopf, Linear optimization queries, Proceedings of the eighth annual symposium on Computational geometry, p.16-25, June 10-12, 1992, Berlin, Germany
	P. Yamamoto , K. Kato , K. Imai , H. Imai, Algorithms for vertical and orthogonal L1 linear approximation of points, Proceedings of the fourth annual symposium on Computational geometry, p.352-361, June 06-08, 1988, Urbana-Champaign, Illinois, United States
	Timothy M. Chan, Deterministic algorithms for 2-d convex programming and 3-d online linear programming, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.464-472, January 05-07, 1997, New Orleans, Louisiana, United States
	A Blumer , A Ehrenfeucht , D Haussler , M Warmuth, Classifying learnable geometric concepts with the Vapnik-Chervonenkis dimension, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.273-282, May 28-30, 1986, Berkeley, California, 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
	Jean-Daniel Boissonnat , Jurek Czyzowicz , Olivier Devillers , Mariette Yvinec, Circular separability of polygon, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.273-281, January 22-24, 1995, San Francisco, California, United States
	Nancy M. Amato , Edgar A. Ramos, On computing Voronoi diagrams by divide-prune-and-conquer, Proceedings of the twelfth annual symposium on Computational geometry, p.166-175, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Pankaj K. Agarwal , Micha Sharir , Sivan Toledo, Applications of parametric searching in geometric optimization, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.72-82, September 1992, Orlando, Florida, United States
	Timothy M. Chan, Fixed-dimensional linear programming queries made easy, Proceedings of the twelfth annual symposium on Computational geometry, p.284-290, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	K. Mulmuley, Output sensitive construction of levels and Voronoi diagrams in Rd of order 1 to k, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.322-330, May 13-17, 1990, Baltimore, Maryland, United States
	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
	Timothy M. Chan, Approximating the diameter, width, smallest enclosing cylinder, and minimum-width annulus, Proceedings of the sixteenth annual symposium on Computational geometry, p.300-309, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	P. Egyed , R. Wenger, Stabbing pairwise disjoint translates in linear time, Proceedings of the fifth annual symposium on Computational geometry, p.364-369, June 05-07, 1989, Saarbruchen, West Germany
	Martin Dyer, A parallel algorithm for linear programming in fixed dimension, Proceedings of the eleventh annual symposium on Computational geometry, p.345-349, June 05-07, 1995, Vancouver, British Columbia, Canada
	Danny Z. Chen , Ovidiu Daescu , Yang Dai , Naoki Katoh , Xiadong Wu , Jinhui Xu, Optimizing the sum of linear fractional functions and applications, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.707-716, January 09-11, 2000, San Francisco, California, United States
	R Seidel, Constructing higher-dimensional convex hulls at logarithmic cost per face, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.404-413, May 28-30, 1986, Berkeley, California, United States
	Pankaj K. Agarwal , Pavan K. Desikan, An efficient algorithm for terrain simplification, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.139-147, January 05-07, 1997, New Orleans, Louisiana, United States
	L. W. Brinn, A polygon matching problem in computer vision (abstract only), Proceedings of the 15th annual conference on Computer Science, p.400, February 1987, St. Louis, Missouri, United States
	Noga Alon , Nimrod Megiddo, Parallel linear programming in fixed dimension almost surely in constant time, Journal of the ACM (JACM), v.41 n.2, p.422-434, 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
	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
	Alexander T. Ishii , Charles E. Leiserson , Marios C. Papaefthymiou, Optimizing two-phase, level-clocked circuitry, Journal of the ACM (JACM), v.44 n.1, p.148-199, Jan. 1997
	Joseph S. B. Mitchell , Subhash Suri, Separation and approximation of polyhedral objects, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.296-306, September 1992, Orlando, Florida, United States
	Miklos Ajtai , Nimrod Megiddo, A deterministic poly(log log N)-time N-processor algorithm for linear programming in fixed dimension, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.327-338, May 04-06, 1992, Victoria, British Columbia, Canada
	Pankaj K. Agarwal , Micha Sharir, Efficient algorithms for geometric optimization, ACM Computing Surveys (CSUR), v.30 n.4, p.412-458, Dec. 1998
	Nir Halman, A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane, Information Processing Letters, v.86 n.3, p.121-128, 16 May 2003
	Binay K. Bhattacharya , Sreesh Jadhav , Asish Mukhopadhayay , Jean-Marc Robert, Optimal algorithms for some smallest intersection radius problems (extended abstract), Proceedings of the seventh annual symposium on Computational geometry, p.81-88, June 10-12, 1991, North Conway, New Hampshire, United States
	Ilan Adler , Peter A. Beling, Polynomial algorithms for linear programming over the algebraic numbers, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.483-494, May 04-06, 1992, Victoria, British Columbia, Canada
	Adrian Dumitrescu , Joseph S. B. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.38-46, January 07-09, 2001, Washington, D.C., United States
	K Clarkson, A probabilistic algorithm for the post office problem, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.175-184, May 06-08, 1985, Providence, Rhode Island, United States
	Christian A. Duncan , Michael T. Goodrich , Edgar A. Ramos, Efficient approximation and optimization algorithms for computational metrology, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.121-130, January 05-07, 1997, New Orleans, Louisiana, United States
	D. G. Kirkpatrick , B. Mishra , C. K. Yap, Quantitative Steinitz's theorems with applications to multifingered grasping, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.341-351, May 13-17, 1990, Baltimore, Maryland, United States
	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
	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
	Timothy M. Chan, Geometric applications of a randomized optimization technique, Proceedings of the fourteenth annual symposium on Computational geometry, p.269-278, June 07-10, 1998, Minneapolis, Minnesota, United States
	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
	David Fernández-Baca, Decomposable multi-parameter matroid optimization problems, Theoretical Computer Science, v.297 n.1-3, p.183-198, 17 March 2003
	Francis Y. L. Chin , Hong Shen , Fu Lee Wang, Transversal of disjoint convex polygons, Information Processing Letters, v.85 n.1, p.55-60, 16 January 2003
	D. Coeurjolly , S. Miguet , L. Tougne, 2D and 3D visibility in discrete geometry: an application to discrete geodesic paths, Pattern Recognition Letters, v.25 n.5, p.561-570, 5 April 2004
	Lilian Buzer, A linear incremental algorithm for naive and standard digital lines and planes recognition, Graphical Models, v.65 n.1-3, p.61-76, January 2003
	Kaspar Fischer , Bernd Gartner, The smallest enclosing ball of balls: combinatorial structure and algorithms, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Michael Hoffmann, A simple linear algorithm for computing rectilinear 3-centers, Computational Geometry: Theory and Applications, v.31 n.3, p.150-165, June 2005
	Timothy M. Chan, An optimal randomized algorithm for maximum Tukey depth, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
	Timothy M. Y. Chan , Jack Snoeyink , Chee-Keng Yap, Output-sensitive construction of polytopes in four dimensions and clipped Voronoi diagrams in three, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.282-291, January 22-24, 1995, San Francisco, California, United States
	Anselm Blumer , A. Ehrenfeucht , David Haussler , Manfred K. Warmuth, Learnability and the Vapnik-Chervonenkis dimension, Journal of the ACM (JACM), v.36 n.4, p.929-965, Oct. 1989
	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
	Joseph S. B. Mitchell , Joseph O'Rourke, Computational geometry, ACM SIGACT News, v.32 n.3, p.63-72, 09/01/2001
	Xiang Lu , Zhuo Li , Wangqi Qiu , D. M. H. Walker , Weiping Shi, Longest path selection for delay test under process variation, Proceedings of the 2004 conference on Asia South Pacific design automation: electronic design and solution fair, p.98-103, January 27-30, 2004, Yokohama, Japan
	Francis Y. L. Chin , Fu Lee Wang, Efficient algorithm for transversal of disjoint convex polygons, Information Processing Letters, v.83 n.3, p.141-144, 16 August 2002
	Wlodzimierz Ogryczak , Arie Tamir, Minimizing the sum of the k largest functions in linear time, Information Processing Letters, v.85 n.3, p.117-122, 14 February 2003
	Hervé Brönnimann , John Iacono , Jyrki Katajainen , Pat Morin , Jason Morrison , Godfried Toussaint, Space-efficient planar convex hull algorithms, Theoretical Computer Science, v.321 n.1, p.25-40, June 16, 2004
	Adrian Dumitrescu , Joseph S. B. Mitchell, Approximation algorithms for TSP with neighborhoods in the plane, Journal of Algorithms, v.48 n.1, p.135-159, August 2003
	Thomas Ottmann , Sven Schuierer , Subbiah Soundaralakshmi, Enumerating extreme points in higher dimensions, Nordic Journal of Computing, v.8 n.2, p.179-192, Summer 2001
	Timothy M. Chan , Eric Y. Chen, Multi-pass geometric algorithms, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	Frank Nielsen , Richard Nock, A fast deterministic smallest enclosing disk approximation algorithm, Information Processing Letters, v.93 n.6, p.263-268, 31 March 2005
	Valentin Brimkov , David Coeurjolly , Reinhard Klette, Digital planarity-A review, Discrete Applied Mathematics, v.155 n.4, p.468-495, February, 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
	Valentin Brimkov, Algorithmic and explicit determination of the Lovász number for certain circulant graphs, Discrete Applied Mathematics, v.155 n.14, p.1812-1825, September, 2007
	Nikolas List , Hans Ulrich Simon, General Polynomial Time Decomposition Algorithms, The Journal of Machine Learning Research, 8, p.303-321, 5/1/2007
	Michael Goldwasser, A survey of linear programming in randomized subexponential time, ACM SIGACT News, v.26 n.2, p.96-104, June 1995
	Pat Morin, An optimal randomized algorithm for d-variate zonoid depth, Computational Geometry: Theory and Applications, v.39 n.3, p.229-235, April, 2008
	David Bremner , Dan Chen , John Iacono , Stefan Langerman , Pat Morin, Output-sensitive algorithms for Tukey depth and related problems, Statistics and Computing, v.18 n.3, p.259-266, September 2008
	Shaohua Pan , Suyan He , Xingsi Li, Smoothing method for minimizing the sum of the r largest functions, Optimization Methods & Software, v.22 n.2, p.267-277, April 2007
	S. Abravaya , D. Berend, Multi-dimensional dynamic facility location and fast computation at query points, Information Processing Letters, v.109 n.8, p.386-390, March, 2009
	David Eppstein , Elena Mumford , Bettina Speckmann , Kevin Verbeek, Area-universal rectangular layouts, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark
	Dror Aiger , Klara Kedem, Geometric pattern matching for point sets in the plane under similarity transformations, Information Processing Letters, v.109 n.16, p.935-940, July, 2009
	Donatas Elvikis , Horst W. Hamacher , Marcel T. Kalsch, Simultaneous scheduling and location (ScheLoc): the planar ScheLoc makespan problem, Journal of Scheduling, v.12 n.4, p.361-374, August 2009