Online and Approximation Algorithms for Clustering and Network Design

• Grant number: 17/11382-2
• Support Opportunities: 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
• 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.

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. (14/18781-1, 15/11937-9, 17/11382-2)