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: