MIT Department of Electrical Engineering & Computer Science

Enhancing techniques in LP based approximation algorithms

Kamal Jain
Georgia Tech

Wednesday, March 8, 2000
4:15 PM (refreshments 4:00)
Room NE43-518
EECS Special Seminar

Abstract

Over the last decade many new approximation algorithms have been developed for NP-hard optimization problems. A large fraction of these are based on linear programming theory. These algorithms use two basic techniques, rounding and primal dual schema. My talk will consist of three parts, the first two discussing enhancements of both these techniques, and the third, adapting the technique of Lagrangian relaxation in the context of approximation algorithms.

First, we introduce the technique of iterative rounding to obtain a factor 2 approximation algorithm for the Generalized Steiner Network problem, thereby settling a long standing open problem. This problem seeks to build the cheapest cost network connecting every pair of nodes by a specified number of edge disjoint paths. This problem arises in the design of survivable networks.

In the context of approximation algorithms, the primal dual schema was applied only when there were no negative coefficients in either the primal or the dual programs. We use this schema to obtain an approximation algorithm for metric facility location problem, thereby extending the schema to linear programs with negative coefficients as well. This problem seeks the cheapest way of locating facilities (e.g., warehouses or proxy webservers) to serve a given set of clients. Our algorithm is time efficient as well.

One limitation of the primal dual schema is that it works locally. So it fails when there is a global constraint, such as a budget constraint. For instance, in the facility location problem, we may be required to open at most k facilities, a special case of which is the k median problem. We adapt the classical technique of Lagrangian relaxation from combinatorial optimization to deal with such situations. Using this we obtain a factor 6 approximation algorithm for the k median problem, which has applications in data mining and web searching.