Approximation Algorithms via Linear Programming

Linear programming has proved to be an extremely useful tool in the design and analysis of approximation algorithms. We will survey a number of recent results along these lines, and will focus on algorithms that start by solving a linear program, and then round an optimal fractional solution to a nearby integer one. Among the results that we shall discuss are algorithms for the generalized assignment problem and the job shop scheduling problem. The linear programs that must be solved have a combinatorial structure; we will discuss how this structure can often be exploited to derive more efficient combinatorial algorithms for these linear programming problems.

References

• David B. Shmoys. Computing near-optimal solutions to combinatorial optimization problems, in: W. Cook, L. Lovasz, and P.D. Seymour (1995). Special Year on Combinatorial Optimization, AMS, Providence, to appear. [This is a survey that contains references to many of the results that I will talk in detail about.]

The following is a partial list of papers on algorithms for fractional packing and covering problems:

• Michael D. Grigoriadis and Leonid G. Khachiyan (1994). Fast approximation schemes for convex programs with many blocks and coupling constraints. SIAM J. on Optimization, 86-107.

• Ravi Kannan, John Mount, and Sridhar Tayur. A randomized algorithm to optimize over certain convex sets. Mathematics of Operations Research, to appear.

• Michael Luby and Noam Nisan (1993). A parallel approximation algorithm for positive linear programming, in: Proceedings of the 25th Annual Symposium on Theory of Computing, 448-457.

• Serge Plotkin, David B. Shmoys, and Eva Tardos. Fast approximation algorithms for fractional packing and covering problems. Mathematics of Operations Research, to appear. [A preliminary version appeared in Proceedings of the 32nd Annual IEEE Symposium on Foundations of Computer Science.]

• Neal E. Young (1995). Randomized rounding without solving the linear program, in: Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 170-178.