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: