Linear Programming in Linear Time When the Dimension Is Fixed
- 1 January 1984
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 31 (1), 114-127
- https://doi.org/10.1145/2422.322418
Abstract
It is demonstrated that the linear programming problem in d variables and n constraints can be solved in O(n) time when d is fixed. This bound follows from a multidimensional search technique which is applicable for quadratic programming as well. There is also developed an algorithm that is polynomial in both n and d provided d is bounded by a certain slowly growing function of n.Keywords
This publication has 5 references indexed in Scilit:
- Is binary encoding appropriate for the problem-language relationship?Theoretical Computer Science, 1982
- Multidimensional divide-and-conquerCommunications of the ACM, 1980
- Combinatorial solutions of multidimensional divide-and-conquer recurrencesJournal of Algorithms, 1980
- Finding the medianJournal of Computer and System Sciences, 1976
- Expected time bounds for selectionCommunications of the ACM, 1975