Scholarship 17/11382-2 - Algoritmos de aproximação, Otimização combinatória - BV FAPESP
Advanced search
Start date
Betweenand

Online and Approximation Algorithms for Clustering and Network Design

Grant number: 17/11382-2
Support Opportunities:Scholarships in Brazil - Post-Doctoral
Start date: September 01, 2017
End date: February 07, 2018
Field of knowledge:Physical Sciences and Mathematics - Computer Science - Theory of Computation
Principal Investigator:Cristina Gomes Fernandes
Grantee:Mário César San Felice
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

This is the research project for the postdoc of Mário César San Felice, to be accomplished at the Institute of Mathematics and Statistics of the University of São Paulo (IME-USP), from August 1, 2017 to July 31, 2019, under the supervision of Professor Cristina Gomes Fernandes. The goal is to address combinatorial optimization problems, aiming at the design and analysis of new algorithms, at the analysis refinement of existing algorithms, and at finding better lower bounds to the problems. The focus will be on clustering problems, in which we have to partition a set of objects according to some similarity criterion, and on network design problems, in which we have to build an infrastructure to satisfy connectivity demands. We are particularly interested in network design problems with two layers, in which we have the option to build two levels of infrastructure with distinct costs and capacities to serve demands of transport or data. The central problem from network design with two layers is the connected facility location problem, which combines the classics Steiner tree and facility location problems with the rent-or-buy model. We intend to approach these problems both in the offline and online settings, respectively, through the approximation algorithms and competitive analysis approaches.

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

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)
DE LIMA, MURILO SANTOS; SAN FELICE, MARIO CESAR; LEE, ORLANDO. Group parking permit problems. DISCRETE APPLIED MATHEMATICS, v. 281, n. SI, p. 172-194, . (14/18781-1, 15/11937-9, 17/11382-2)
DADALTO, ARTHUR PRATTI; USBERTI, FABIO LUIZ; SAN FELICE, MARIO CESAR. Exact approaches for the Minimum Subgraph Diameter Problem. Computers & Operations Research, v. 150, p. 10-pg., . (15/11937-9, 17/11382-2)
DE LIMA, MURILO SANTOS; SAN FELICE, MARIO CESAR; LEE, ORLANDO. Group parking permit problems. DISCRETE APPLIED MATHEMATICS, v. 281, p. 23-pg., . (14/18781-1, 15/11937-9, 17/11382-2)