A topic in the Open Knowledge Graph — a free, open map of 15,290 topics and the order to learn them in.
Linear programming (LP) optimizes a linear objective function subject to linear inequality constraints. The simplex method, developed by Dantzig (1947), traverses vertices of the feasible polytope along improving edges — it is exponential in worst case but extraordinarily fast in practice. Interior point methods, introduced by Karmarkar (1984), traverse the interior of the polytope using barrier functions and achieve polynomial worst-case complexity O(n3.5 L) for n variables and L input bits. The ellipsoid method (Khachiyan, 1979) proved LP is in P but is impractical. Modern LP solvers combine these approaches: simplex for warm-starting and sensitivity analysis, interior point for large-scale instances. LP is the backbone of combinatorial optimization — it underpins network flow, matching, approximation algorithms, and scheduling.
Linear programming is arguably the most important optimization framework in computer science. The problem is deceptively simple: maximize (or minimize) a linear function cT x subject to Ax <= b and x >= 0. Despite the simplicity of the formulation, LP captures an enormous range of practical problems — network flows, resource allocation, scheduling, and transportation — and serves as the foundation for integer programming and approximation algorithms.
The simplex method, the first practical LP algorithm, walks along the edges of the feasible polytope from vertex to vertex, always moving to a neighbor with a better objective value. Each step (pivot) changes one variable from its bound, and the method terminates at a vertex where no neighbor improves the objective. In the worst case, the method visits exponentially many vertices (the Klee-Minty cube construction forces 2n pivots on an n-variable LP). Yet in practice, simplex typically performs O(n) to O(n2) pivots. Spielman and Teng's smoothed analysis explains this: under tiny random perturbations, the expected number of pivots is polynomial, and real-world instances always contain such perturbations from measurement noise or floating-point arithmetic.
Interior point methods take a fundamentally different approach. Instead of walking along the boundary, they traverse the interior of the polytope using a barrier function that repels the trajectory from the constraints. At each iteration, the barrier parameter decreases and the trajectory converges to the optimal vertex. Each iteration requires solving an n-by-n linear system, making it expensive per step — but the number of iterations is O(sqrt(n) * log(1/epsilon)) to reach epsilon-optimality, giving polynomial total complexity. For large, sparse LPs where the linear system has exploitable structure, interior point methods are dramatically faster than simplex.
LP duality is the theoretical engine behind approximation algorithms and economic interpretations. Every LP (the "primal") has a "dual" LP with the same optimal value (strong duality). The dual variables have natural interpretations: in a resource allocation LP, dual variables are "shadow prices" reflecting the marginal value of each resource constraint. Complementary slackness conditions relate optimal primal and dual solutions, enabling the primal-dual method for approximation algorithms. The totality of LP theory — duality, sensitivity analysis, the simplex method, and polynomial-time solvability — makes LP the single most versatile tool in the algorithm designer's toolkit.