Experimental and combinatorial optimization methods for the tropical subset proble...
Discrete optimization and graphs: algorithms, theory and applications
Grant number: | 22/15632-1 |
Support Opportunities: | Scholarships abroad - Research Internship - Master's degree |
Effective date (Start): | February 01, 2023 |
Effective date (End): | May 31, 2023 |
Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
Principal Investigator: | Yoshiko Wakabayashi |
Grantee: | Gabriel Morete de Azevedo |
Supervisor: | Joseph Cheriyan |
Host Institution: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil |
Research place: | University of Waterloo, Canada |
Associated to the scholarship: | 21/12599-0 - Connectivity augmentation in graphs and robust networks, BP.MS |
Abstract This is the BEPE-MS research proposal of Gabriel Morete de Azevedo, M.Sc. studentat the Institute of Mathematics and Statistics of the University of São Paulo, to be conducted at the Combinatorics & Optimization Department of the University of Waterloo,under the supervision of Professor Joseph Cheriyan. It is a project in combinatorial optimization that addresses problems on connectivity augmentation of graphs, with emphasis on their algorithmic aspects. Generally speaking, the goal of the problems to be investigated is to increase the connectivity of an input graph, by adding edges from a given set of links with non-negative costs, while minimizing the total cost. Some variants of these problems will be investigated, considering vertex-connectivity or edge-connectivity. When the graph models, for example, a telecommunication or a power transmission network, these parameters indicate the robustness (degree of fault tolerance) of the network, being of great interest both from practical and theoretical viewpoint. In general, such problems are all computationally difficult. By studying many different problems and algorithms, the candidate will be exposed to several techniques that are important to build a solid background in combinatorial optimization, in particular, in design of approximation algorithms. | |
News published in Agência FAPESP Newsletter about the scholarship: | |
TITULO | |
Articles published in other media outlets (0 total): | |
More itemsLess items | |
VEICULO: TITULO (DATA) | |
VEICULO: TITULO (DATA) | |