Árvores de Steiner de Grupos

Resumo: O problema da árvore de Steiner de grupos (Group Steiner Tree - GST) consiste no seguinte: dados um grafo com pesos nas arestas, um inteiro k e k conjuntos de vértices - os grupos - encontrar uma árvore de peso mínimo que contenha um elemento de cada grupo.

O problema da cobertura mínima por conjuntos (Set Cover) é um caso particular desse e, a menos que P=NP, não há o(log k)-aproximação para o GST. Mostraremos um algoritmo de aproximação com razão polilogarítmica para o GST, devido a Garg, Konjevod e Ravi. O algoritmo é probabilístico e baseia-se em um resultado de Bartal que permite reduzir o problema de grafos para árvores (com uma perda polilogarítmica na razão de aproximação). A resolução (aproximada) do GST em árvores baseia-se em programação linear. Esse é o algoritmo de aproximação com a melhor razão conhecida para o GST até o momento.