Advanced search
Start date

Approximation Algorithms for Hub-Location Problems

Grant number: 16/12006-1
Support type:Scholarships in Brazil - Master
Effective date (Start): September 01, 2016
Effective date (End): 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
Home Institution: Instituto de Computação (IC). Universidade Estadual de Campinas (UNICAMP). Campinas , SP, Brazil


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.

Scientific publications
(References retrieved automatically from Web of Science and SciELO through information on FAPESP grants and their corresponding numbers as mentioned in the publications by the authors)
BENEDITO, MARCELO P. L.; PEDROSA, LEHILTON L. C. Approximation algorithms for Median Hub Location Problems. JOURNAL OF COMBINATORIAL OPTIMIZATION, v. 38, n. 2, p. 375-401, AUG 2019. Web of Science Citations: 0.
Academic Publications
(References retrieved automatically from State of São Paulo Research Institutions)
BENEDITO, Marcelo Pinheiro Leite. Algoritmos de aproximação para problemas de localização e alocação de terminais. 2018. Master's Dissertation.

Please report errors in scientific publications list by writing to: