A new polynomial-time algorithm for linear programming
For decades the main linear-programming algorithm was the Simplex method, fast in practice but exponential in the worst case. Whether a polynomial-time algorithm existed was a major open problem.
Proposes an interior-point method: unlike Simplex, which travels along the edges of the feasible region, Karmarkar's algorithm proceeds through the interior using projective transformations.
Proved the algorithm runs in polynomial time, answering the open question, and claimed practical speed advantages over Simplex for large problems.
Practical performance claims were initially contested; highly optimized Simplex solvers remained competitive for many problem types for years.
For the humanoid robot, control-theory and motion-planning problems (e.g. joint-angle trajectories that keep balance) are often formulated as convex problems solvable by interior-point methods; for the software agent, resource-allocation tasks can be convex too.
📇 Summary flashcard — 13 analytical fields for this paper
خلاصه
Introduced a groundbreaking interior-point method for linear programming, proving polynomial-time solvability.
نمای سریع
Karmarkar's algorithm moves through the interior of the solution space rather than along its edges.
یافتههای کلیدی
Proved the algorithm runs in polynomial time, answering the open question, and claimed practical speed advantages over Simplex for large problems.
هدف
Find a provably polynomial-time algorithm for linear programming.
روش
Proposes an interior-point method: unlike Simplex, which travels along the edges of the feasible region, Karmarkar's algorithm proceeds through the interior using projective transformations.
نتایج
First such algorithm, also claimed practically efficient, launching the field of interior-point methods.
نتیجهگیری
Linear programming is fundamentally tractable ('P'), with broad implications for optimization-reliant fields.
مفاهیم کلیدی
convex-optimization، linear-programming، interior-point-methods، algorithms، computational-complexity
مطالعهی بیشتر
https://doi.org/10.1007/BF02579150
تحلیل
A landmark of theoretical computer science with immediate large practical impact (notably at AT&T).
محدودیتها
Practical performance claims were initially contested; highly optimized Simplex solvers remained competitive for many problem types for years.
کارهای آینده
Extending interior-point methods to quadratic and semidefinite programming.
کاربرد عملی
For the humanoid robot, control-theory and motion-planning problems (e.g. joint-angle trajectories that keep balance) are often formulated as convex problems solvable by interior-point methods; for the software agent, resource-allocation tasks can be convex too.
◀ References (this paper draws on) (0)
No references recorded.
Cited by (0) ▶
No paper cites this one yet.
Prerequisite learning path for this paper