Approximation algorithms for the facility location problem

Abstract

In the Facility Location Problem, it is sought to decide how many and which facilities to open in order to serve the connection demands of the clients. It is very relevant both due to its theoretical difficulty, being a NP-hard problem widely studied and for which numerous approximation algorithms are known, as well as for being motivated by practical applications, modeling problems such as plant positioning, construction of computer networks and information clustering. This project has as objectives the study of approximation algorithms for the Facility Location Problem, the implementation of some of these algorithms, and the production of a technical report with the studied results, which may be used by other researchers and students in the field. This scientific initiation also aims to introduce the candidate to the area of scientific research as well as to complement her training in the area of Computer Science, deepening her knowledge in combinatorial optimization, approximation algorithms and techniques of design and analysis of algorithms.