| 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, both of these were enhanced to give new approximation algorithms. The thesis consists 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.;The technique of iterative rounding was introduced 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 had been applied only when there were no negative coefficients in either the primal or the dual programs. The schema was used for the first time to obtain an approximation algorithm for the metric facility location problem, thereby extending the schema to linear programs with negative coefficients as well. This was also the first practical approximation algorithm for this four decade old problem. This problem seeks the cheapest way of locating facilities (e.g., warehouses or proxy webservers) to serve a given set of clients.;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. The classical technique of Lagrangian relaxation from combinatorial optimization was adapted to deal with such situations. This technique was used to obtain a factor 6 approximation algorithm for the k median problem. This has applications in data mining and web searching. |
