Advanced search
Start date
Betweenand

The Prize-Collecting Steiner tree problem

Grant number: 20/10341-3
Support type: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 researcher:Carlos Eduardo Ferreira
Grantee:Gabriel Morete de Azevedo
Home 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:
Articles published in other media outlets (0 total):
More itemsLess items
VEICULO: TITULO (DATA)
VEICULO: TITULO (DATA)