Advanced search
Start date

The Prize-Collecting Steiner tree problem

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


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:
Articles published in other media outlets (0 total):
More itemsLess items

Please report errors in scientific publications list by writing to: