Approximation Algorithms via Linear Programming:
Three Easy Results
The
past ten years has seen a veritable explosion in our understanding of the
role that linear programming plays in the design and analysis of approximation
algorithms. We will present some recent examples in which this viewpoint
provides a simple means of obtaining strong performance guarantees on the
relative error of algorithms for a variety of combinatorial optimization
problems. Among the examples we shall discuss are variants of the partial latin
square completion problem, the joint replenishment problem in the discrete
finite-time horizon with deterministic non-stationary demand, and the
uncapacitated facility location problem.
The three papers on which this
talk is based are joint work, respectively, with Carla Gomes and Rommel Regis,
Retsef Levi and Robin Roundy, and Aaron Archer and Ranjith Rajogopalan.