Advanced search
Start date
Betweenand

Approximation algorithms for the facility location problem

Grant number: 18/13083-5
Support type:Scholarships in Brazil - Scientific Initiation
Effective date (Start): October 01, 2018
Effective date (End): June 30, 2020
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal researcher:Mário César San Felice
Grantee:Renata Sarmet Smiderle Mendes
Home Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil
Associated scholarship(s):19/16276-1 - Combining approximation algorithms with metaheuristics for the facility location problem, BE.EP.IC

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.