Primal-Dual Algorithms for Combinatorial Optimization Problems

Abstract

Combinatorial optimization problems such as routing, scheduling, covering and packing problems abound in everyday life. At a very high level, a combinatorial optimization problem amounts to finding a solution with minimum or maximum cost among a large number of feasible solutions. An algorithm for a given optimization problem is said to be exact if it always returns an optimal solution and is said to be efficient if it runs in time polynomial on the size of its input. The theory of NP-completeness suggests that exact and efficient algorithms are unlikely to exist for the class of NP-hard problems. Unfortunately, a large number of natural and interesting combinatorial optimization problems are NP-hard.

One way to cope with NP-hardness is to relax the optimality requirement and instead look for solutions that are provably close to the optimum. This is the main idea behind approximation algorithms. An algorithm is said to be an r-approximation if it always returns a solution whose cost is at most an r factor away from the optimal cost.

Arguably, one of the most important techniques in the design of combinatorial algorithms is the primal-dual schema in which the cost of the primal solution is compared to the cost of a dual solution. In this dissertation we study the primal-dual schema in the design of approximation algorithms for a number of covering and scheduling problems.