Advanced search
Start date
Betweenand

Online and Approximation Algorithms for Clustering and Network Design

Grant number: 17/11382-2
Support type:Scholarships in Brazil - Post-Doctorate
Effective date (Start): September 01, 2017
Effective date (End): 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
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

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.

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, JUL 15 2020. Web of Science Citations: 0.

Please report errors in scientific publications list by writing to: cdi@fapesp.br.