Advanced search
Start date

Approximation algorithms for hub-location problems

Grant number: 16/12006-1
Support Opportunities: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
Host 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. (AU)

News published in Agência FAPESP Newsletter about the scholarship:
Articles published in other media outlets (0 total):
More itemsLess items

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, . (16/12006-1, 15/11937-9)
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 - Universidade Estadual de Campinas (UNICAMP). Instituto de Computação Campinas, SP.

Please report errors in scientific publications list by writing to: