Approximation algorithms for network design problems with restrictions

• Grant number: 14/14209-1
• Support Opportunities: Scholarships in Brazil - Post-Doctoral
• Start date: November 01, 2014
• End date: July 31, 2015
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Agreement: Coordination of Improvement of Higher Education Personnel (CAPES)
• Principal Investigator: Cristina Gomes Fernandes
• Grantee: Lehilton Lelis Chaves Pedrosa
• Host 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

Abstract

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. (13/03447-6, 14/14209-1)

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. (14/14209-1, 13/21744-8)

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, p. 32-pg., 2018-03-01. (14/14209-1, 13/03447-6)