Linear Programming in Linear Time When the Dimension Is Fixed

1984/01/01 by Nimrod Megiddo · 11 citations
Computer Science · #Data Management and Algorithms #Constraint Satisfaction and Optimization #Optimization and Search Problems

paper · pdf · doi:10.1145/2422.322418

openalex publication_date 1984/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/22

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.

Cited by

• A condition number analysis of an algorithm for solving a system of polynomial equations with one degree of freedom
• The NP-completeness column: An ongoing guide
• A Linear Time Algorithm for the Maximum Overlap of Two Convex Polygons Under Translation
• Learnability and the Vapnik-Chervonenkis dimension
• Partitioning with two lines in the plane
• Hitting and Covering Affine Families of Convex Polyhedra, with Applications to Robust Optimization
• Applications of random sampling in computational geometry, II
• Optimal Algorithms for Separating a Polyhedron from Its Single-Part Mold
• The k-Center Problem of Uncertain Points on Graphs
• Strongly polynomial-time and NC algorithms for detecting cycles in dynamic graphs
• Prune and search [wikipedia]