A computational study for the Prize-Collecting dominating cycle problem
Online and Approximation Algorithms for Clustering and Network Design
Lagrangean algorithms to the problem of minimum spanning tree dilatation in a geom...
| Grant number: | 20/10341-3 |
| Support Opportunities: | Scholarships in Brazil - Scientific Initiation |
| Effective date (Start): | September 01, 2020 |
| Effective date (End): | July 31, 2021 |
| Field of knowledge: | Physical Sciences and Mathematics - Computer Science - Theory of Computation |
| Principal Investigator: | Carlos Eduardo Ferreira |
| Grantee: | Gabriel Morete de Azevedo |
| Host Institution: | Instituto de Matemática e Estatística (IME). Universidade de São Paulo (USP). São Paulo , SP, Brazil |
Abstract This is an undergraduate research project to be carried out at IME-USP from 01/08/2020 to 30/7/2021. The main goal of this project is to study the prize-collecting Steiner tree problem, a well-known generalization of the Steiner tree problem in graphs which has many applications. The study includes formulations, exact approaches, and approximations. Moreover, the student will be familiarized with topics from combinatorial optimization such as design of algorithms, computational complexity, and inapproximability. | |
| 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) | |