MSc thesis of Άννα Κουτλή
Προσεγγιστικοί αλγόριθμοι για ανάθεση πόρων σε δίκτυα
Supervisor: Βασίλειος Ζησιμόπουλος
Resource Allocation Problems are of particular importance not only from a theo- retical 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 min- imizing 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 comparison 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 Location 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: 22 Ιουλίου 2015.