Karmarkar's algorithm, introduced by Narendra Karmarkar in 1984, solves linear programming problems and was the first reasonably efficient algorithm shown to solve them in polynomial time. It works from the interior of the feasible region rather than moving along its boundary as the earlier simplex method does. The previously known ellipsoid method was also polynomial time, but proved impractical, and Karmarkar's algorithm's practical efficiency helped launch the broader family of interior point methods.
Facts
Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Connections
Credited To
Source Karmarkar's Algorithm (Wikipedia)
In Field
Source Karmarkar's Algorithm (Wikipedia)
Invented By
Narendra Karmarkar published his interior-point method for linear programming in 1984.
Sources
1. Karmarkar's Algorithm (Wikipedia)
Wikipedia infobox: time complexity polynomial
polynomial
Credited To: Narendra Karmarkar, Intro, lead sentence
Narendra Karmarkar
In Field: Algorithms and Complexity Theory, Lead sentence
Karmarkar's algorithm is an algorithm introduced by Narendra Karmarkar in 1984 for solving linear programming problems.
In Group: Linear Programming Algorithms, Lead section
for solving linear programming problems
View the SourceWikidata: Karmarkar's Algorithm
Wikidata Q2246305, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.