Blog · Collection
Design and analysis of algorithms
Linear programming and duality, network flows, approximation algorithms, randomized algorithms, high-dimensional geometry and spectral graph theory.
Linear programming and duality
Linear programs, , are the common language of much of algorithm design. The simplex method walks along the vertices of the feasible region, while the ellipsoid and interior-point methods run in polynomial time. Every linear program has a dual, and strong duality says their optimal values are equal. The dual often has a natural meaning, such as prices for the constraints or a certificate that a solution is optimal.
Network flows
The max-flow min-cut theorem is linear programming duality in combinatorial form: the largest flow from to equals the capacity of the smallest cut separating them. Augmenting-path algorithms compute it, and min-cost flow extends the idea to transportation and assignment problems.
Approximation algorithms
Many important problems are NP-hard, so the goal becomes a provable approximation ratio. Solving a linear programming relaxation and then rounding gives a 2-approximation for vertex cover and a logarithmic one for set cover. The primal-dual method builds a solution and a matching lower bound at the same time. Semidefinite programming with random-hyperplane rounding gives the Goemans–Williamson 0.878-approximation for max-cut, and local search handles clustering problems such as -means.
Randomized algorithms
Randomness often makes algorithms simpler and easier to analyze. Universal hashing gives dictionaries with constant expected time per operation, and Karger’s contraction algorithm finds a global minimum cut. Polynomial identity testing checks whether a polynomial is identically zero by evaluating it at random points, justified by the Schwartz–Zippel lemma. Random walks on graphs connect to electrical networks and hitting times.
High dimensions and spectra
Nearest-neighbor search in high dimensions motivates the Johnson–Lindenstrauss lemma, which maps points into dimensions while preserving every pairwise distance to within a factor of . Locality-sensitive hashing and streaming sketches likewise summarize huge data sets in little space. Spectral graph theory completes the picture: the eigenvalues of a graph’s Laplacian measure how well connected it is, which explains both spectral clustering and how quickly random walks mix.