Font size: Αα Αα Αα hide gadgets
You are here: Theses » MSc » Άννα Κουτλή

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.

Scientific committee


Download thesis.


Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.