Approximation Algorithms for Network Problems II

The high level goal of this project is to design efficient (i.e. worst-case polynomial-time) approximation algorithms, with a special focus on NP-hard optimization problems arising from network applications. Informally, a rho-approximation algorithm is an algorithm that provides a solution whose cost is guaranteed to be within a factor rho>= 1 (approximation factor) from the optimal cost. The basic goal is to make rho as small as possible. We will study a family of fundamental network covering, (geometric) network packing, and network pricing problems.