The Prize-Collecting Steiner tree problem

• Grant number: 20/10341-3
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: September 01, 2020
• End date: 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.