Uma Aproximação para o Problema de Alocação de Terminais

No problema de centros dos p-terminais são dados um espaço métrico (V, d) e um conjunto D ⊆ V2 que representa demandas de fluxo. O objetivo é selecionar um subconjunto de V de tamanho p, denominado terminais, e associar cada demanda uv ∈ D a um terminal w, de forma a minimizar o maior custo de percurso entre uma origem u, o terminal associado w e o destino v. Embora os problemas de alocação de terminais componham uma área bastante ativa nos últimos anos, ainda há poucos trabalhos de aproximação. Para o problema de centros dos p-terminais, nós verificamos um limitante inferior de 2 para o fator e obtemos um primeiro algoritmo de aproximação, com fator 3.