On this page
In CBSE Class 12 you solve linear programming problems by drawing the feasible region and checking its corners. That works for two variables. Airlines, telecom networks and refineries solve the same kind of problem with thousands of variables. In 1984 an Indian mathematician, Narendra Karmarkar, found a new way to do it. This post explains his idea with a worked CBSE-style example, and what you can take from how he worked.
Who is Narendra Karmarkar?
A profile on the IIT Bombay alumni website describes him as a 1978 BTech graduate in electrical engineering. In 1984, while working at Bell Labs in New Jersey, he published the result this post is about.
What is linear programming, and how was it solved before?
The same profile gives the history. Linear programming means maximising or minimising a linear function subject to linear constraints. It grew up in the 1940s to plan complex wartime operations. George Dantzig devised the simplex method in 1947, and John von Neumann set out the theory of duality the same year. The 1975 Nobel Prize in economics went to Leonid Kantorovich and Tjalling Koopmans for work on the optimal allocation of resources, in which linear programming played a key role.
The simplex method moves from vertex to vertex along the boundary of the feasible region, improving the objective each time. In practice it is fast, but in some contrived cases the number of steps can grow exponentially with the number of variables. In 1979 Leonid Khachiyan's ellipsoid method guaranteed a polynomial number of steps, but in practice it was much slower than simplex.
What did Karmarkar change?
His 1984 paper, A new polynomial-time algorithm for linear programming, first appeared at the ACM Symposium on Theory of Computing, and a full version followed in Combinatorica the same year. The abstract gives the running time as O(n^3.5 L^2), compared with O(n^6 L^2) for the ellipsoid algorithm. The method repeatedly applies a projective transformation to the feasible region and then optimises over a sphere drawn inside it, producing a sequence of interior points that converges to the optimum.
The IIT Bombay profile sums up the effect. His interior-point method combined the theoretical guarantee of the ellipsoid method with practical speed, and set off an explosion of interior-point methods. These pass through the interior of the feasible region rather than along its edges.
Worked example: corners, edges and the interior
The current NCERT Class 12 Mathematics chapter 12, Linear Programming (2026-27 reprint), states the key theorem: if a bounded feasible region has an optimal value, it occurs at a corner point.
Maximise Z = 2x + 3y subject to x + y ≤ 4, x + 3y ≤ 6, x ≥ 0, y ≥ 0.
Find the corners. The axes give (0, 0). On y = 0, x + y ≤ 4 gives (4, 0). On x = 0, x + 3y ≤ 6 gives (0, 2). The two lines meet where x + y = 4 and x + 3y = 6. Subtract: 2y = 2, so y = 1 and x = 3, giving (3, 1).
Check each corner. Z(0, 0) = 0. Z(4, 0) = 8. Z(3, 1) = 6 + 3 = 9. Z(0, 2) = 6.
Answer. The maximum is Z = 9 at (3, 1).
A simplex-style path would go (0, 0) to (4, 0) to (3, 1), along the edges, improving Z at each step. An interior-point method would start at a point strictly inside, such as (1, 0.5), which satisfies both constraints (1.5 ≤ 4 and 2.5 ≤ 6), and move through the interior towards (3, 1).
Why does the running time matter? For n = 100, compare n^6 with n^3.5. The ratio is n^2.5 = 100^2.5 = 100,000. For large problems, a lower power of n makes a very big difference.
Common mistakes to avoid:
Missing a corner. Always include the corners on the axes as well as the intersections of the constraint lines.
Forgetting x ≥ 0 and y ≥ 0. Without them the region is not the one in the question.
Assuming an unbounded region always has a maximum. NCERT's second theorem says the optimum may not exist when the region is unbounded, so check it.
For more practice with feasible regions, see our guide to linear programming in CBSE Class 12.
What recognition did the work receive?
The ACM gave Karmarkar the Paris Kanellakis Theory and Practice Award, listed among its 2000 citations, for devising an interior-point method that provably runs in polynomial time and for implementation work suggesting it could be effective in practice as well as theory. The citation says these contributions "inspired a renaissance in the theory and practice of linear programming", leading to large improvements in widely used commercial optimisation software.
What can a student learn from how Karmarkar worked?
Question the standard method. Simplex had worked for decades; he asked whether walking along edges was the only way.
Join theory and practice. The award citation praises both his proof and his implementation work.
Use geometry to think. His method is a geometric idea: reshape the region, then step inside a sphere.
If you get stuck finding corner points or setting up constraints, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer.
Redo the worked example with Z = 3x + 2y, find the new optimal corner, and check whether it is still (3, 1).
