Advanced search
Start date

Approximation algorithms for network design problems with restrictions

Grant number: 14/14209-1
Support type:Scholarships in Brazil - Post-Doctorate
Effective date (Start): November 01, 2014
Effective date (End): July 31, 2015
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Cooperation agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
Principal Investigator:Cristina Gomes Fernandes
Grantee:Lehilton Lelis Chaves Pedrosa
Home Institution: Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil
Associated research grant:13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science, AP.TEM


The aim of this post-doctorate project is to study and to obtain approximation algorithms or inapproximability results for combinatorial optimization problems, specially those related to network design under more realistic constraints.The classical network design problems, such as k-center, k-median and facility location have a wide list of applications, such as router allocation, network distribution and many others. They are extensively studied under both the theoretical and practical perspectives. Nevertheless, many times, more realistic restrictions must be imposed to the basic models, such as limiting a router's capacity. Whilst traditional problems without restrictions are well understood, with several proposed approximation algorithms, the versions with restrictions have challenged researchers, and less algorithms have been proposed for them. For example, although a 2-approximation for the k-center is known since the 80's, and it is the best possible under the hypothesis of PP ` NP, the first constant-factor approximation for the capacitated k-center was not discovered until 2012; for the capacitated k-median, no approximation is currently known.Recently, new techniques, specially those based on linear programming, have shown promising results for problems subject to restrictions. The post-doctorate candidate has a deep knowledge on network design problems and linear programming techniques, and has obtained several related results in his doctorate thesis. Thus, this project brings an opportunity to combine the candidate's background and the supervisor's experience, and to unveil results on approximation algorithms that are now over the knowledge boundary. (AU)

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)
FERNANDES, CRISTINA G.; DE PAULA, SAMUEL P.; PEDROSA, LEHILTON L. C. Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. ALGORITHMICA, v. 80, n. 3, SI, p. 1041-1072, MAR 2018. Web of Science Citations: 2.
MIYAZAWA, FLAVIO K.; PEDROSA, LEHILTON L. C.; SCHOUERY, RAFAEL C. S.; DE SOUZA, RENATA G. D. A PTAS for the Geometric Connected Facility Location Problem. THEORY OF COMPUTING SYSTEMS, v. 61, n. 3, p. 871-892, OCT 2017. Web of Science Citations: 0.

Please report errors in scientific publications list by writing to: