UC Riverside

In this thesis we study the Fault-Tolerant Facility Placement problem (FTFP). In the FTFP problem, we are given a set of sites at which we can open facilities, and a set of clients with demands. To satisfy demands, clients must be connected to open facilities. The goal is to satisfy all clients' demands while minimizing the combined cost of opening facilities and connecting clients to facilities. The problem is NP-hard and hence we study approximation algorithms and their performance guarantees. Approximation algorithms are algorithms that run in polynomial time with provable performance bounds relative to optimal solutions.

We present two techniques with which we develop several LP-rounding algorithms with progressively improved approximation ratios. The best ratio we have is 1.575. We also study primal-dual approaches. In particular, we show that a natural greedy algorithm analyzed using the dual-fitting technique gives an approximation ratio of O(log n). On the negative side, under a natural assumption, we give an example showing that the dual-fitting analysis cannot give a ratio better than O(log n / log log n).