MSc thesis of Anna Koutli
Approximation Algorithms on Network Resource Allocation
Supervisor: Vassilis Zissimopoulos
Resource Allocation Problems are of particular importance not only from a theoretical aspect, but also due to their applications in network design. A central place in this area have occupied the so called Facility Location Problems, where given a set of facilities with opening costs and a set of clients with service demands and their respective connection costs, the objective is to satisfy the clients’ demands while minimizing the total cost. This line of problems dates back to the 60’s, however it was not until the mid-90’s that a breakthrough was made in terms of approximation. Since then, numerous variants and results have appeared. In this work, some of the most representative variants are examined followed by a compar- ison of the techniques employed so far to tackle them, most prominently LP-based techniques and local search. We begin by a thorough presentation of the basic Uncapacitated Facility Lo- cation Problem and then continue with the more generic Fault-Tolerant setting. We proceed by analyzing a capacitated version, a variant with outliers and generalizations of the original problem. Finally, we examine the case where the notion of time is introduced, leading to Facility Leasing Problems.Defended: July 22, 2015.