Método Primal-Dual aplicado ao Prize-Collecting Steiner Tree Problem

Resumo: O Prize-Collecting Steiner Tree Problem consiste do seguinte: dado um grafo G com custo nas arestas e penalidade nos vértices, encontrar uma árvore T em G tal que a soma dos custos das arestas de T e das penalidades dos vértices que não estão em T seja mínima.

Mostraremos como o método primal-dual pode ser usado para dar uma 2-aproximação para este problema.

De forma análoga, o método pode ser usado para dar uma 2-aproximação para o Prize-Collecting TSP.

Este seminário baseia-se na Seção 4.8.2 do livro Approximation Algorithms for NP-Hard Problems, editado pela Dorit S. Hochbaum.