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, min⁡{c⊤x:Ax≥b, x≥0}\min\{c^\top x : Ax \ge b,\ x \ge 0\}, 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 ss to tt 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 kk-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 nn points into O(log⁡n/ε2)O(\log n / \varepsilon^2) dimensions while preserving every pairwise distance to within a factor of 1±ε1 \pm \varepsilon. 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.

← All collections