| Grant number: | 16/12006-1 |
| Support Opportunities: | Scholarships in Brazil - Master |
| Start date: | September 01, 2016 |
| End date: | February 28, 2018 |
| Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
| Principal Investigator: | Lehilton Lelis Chaves Pedrosa |
| Grantee: | Marcelo Pinheiro Leite Benedito |
| Host Institution: | Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil |
Abstract Approximation algorithms are applied to combinatorial optimization problems, with the goal of efficiently obtaining solutions with guaranteed quality. The study of such algorithms leads to theoretical results that reveals a problem's structure and computational difficulty. In this project, we will investigate hub location problems (HLP) under the view of approximation algorithms. Given a set of demands between origin-destination pairs, the objective is to locate and install hubs, and assign to each demand a path going through one or more hubs. Such problems appear in situations where it is beneficial routing demands through hubs, as is the case of airport networks. This project's objective is exploring approximation techniques successfully applied to classical location problems, such as the Facility Location Problem, and apply them to hub-location problems, for which there are few approximation algorithms. Implementing interesting algorithms or heuristics is also considered, for they may be used for comparison and problem investigation. Specifically, we will study particular cases of HLPs, such as the p-Hub Median Problem, aiming at new theoretical results in approximation algorithms. (AU) | |
| News published in Agência FAPESP Newsletter about the scholarship: | |
| More itemsLess items | |
| TITULO | |
| Articles published in other media outlets ( ): | |
| More itemsLess items | |
| VEICULO: TITULO (DATA) | |
| VEICULO: TITULO (DATA) | |