Paulo Feofiloff
IME-USP
Sextas-feiras, 29 de setembro e 6 de outubro de 2000, 14:00
Sala 268, Bloco A, IME-USP
Resumo: O problema k-MST (Minimum Spanning k-Tree) consiste no seguinte:
Dado um grafo G, uma função não-negativa c sobre EG,
e um número natural k, encontrar uma subárvore T de G
que minimize c(T) e tenha pelo menos k vértices.
O problema é completo em NP. Blum, Ravi e Vempala inventaram um algoritmo polinomial que determina uma solução aproximada, com fator de aproximação constante. Uma variante simplificada do algoritmo tem fator de aproximação log k. Os algoritmos dependem do método primal-dual de Goemans e Williamson.
Blum, Ravi e Vempala, "A constant-factor approximation algorithm for the k-MST problem", J. Computer and Systems Sciences, 58, pp.101-108, 1999.
Goemans e Williamson, "A general approximation technique for constrained forests problems", SIAM J. Comput., 24, pp.296-317, 1995.