Font size: Αα Αα Αα hide gadgets
You are here: Defenses » July 2015 » Anna Koutli
download defense details: { pdf }

MSc thesis defense presentation

Anna Koutli defends her MSc thesis.

Date: Wednesday, 22 Jul 2015
Time: 17:00-18:00
Location: Department of Informatics, University of Athens, A56
Thesis title: Approximation Algorithms on Network Resource Allocation

Thesis abstract

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.


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