Title: Algoritmos para o problema da árvore de Steiner com coleta de prêmios
Abstract: Algorithms for the prize-collecting Steiner tree problemIn this project we analyze approximation algorithms for the prize-collecting Steiner tree problem.This is a generalization of the Steiner tree problem, in which it is given a graph with positive costs in edges and positive penalties in vertices.The goal is to nd a subtree of the graph that minimizes the sum of costs of edges plus the sum of the penalties of the vertices that don't belong to the subtree.In 2009, the authors Archer, Bateni, Hajiaghayi e Karlo described for the rst time an algorithm with approximation factor strictly less than 2.Besides analyzing this algorithm, we also study the implementation of 2-approximation algorithms for the Steiner tree problem and prize-collecting Steiner tree problem.