Paulo Feofiloff
IME-USP
Sexta-feira, 10 de maio de 2002, 15:30
Sala 267, Bloco A, IME-USP
Resumo:
O problema kMST consiste no seguinte:
dado um grafo com custos nas arestas,
encontrar uma subárvore de custo mínimo
com pelo menos k vértices.
O problema é NP-difícil.
Garg
[A 3-approximation for the minimum tree spanning k vertices,
37th FoCS, 1996]
construiu uma 3-aproximação para o problema
baseada na aproximação primal-dual de Goemans e Williamson
para o problema PCST (Prize-Collection Steiner Tree).
Mais recentemente, Chudak, Roughgarden e Williamson [Approximate k-MSTs and k-Steiner Trees via Primal-Dual Methods and Lagrangean Relaxation, LNCS 2081, 2001] mostraram que o método de Garg pode ser visto como uma relaxação lagrangeana do PCST.
Esta palestra pretende dar uma introdução ao problema kMST e expor parte do artigo de Chudak, Roughgarden e Williamson.