Uma Aproximação para o Problema de Alocação de Terminais - Pedrosa, Lehilton L. C.; dos Santos, Vinícius F.; Schouery, Rafael C. S. (Anais do Encontro de Teoria da Computação (ETC); 2016: Anais do I Encontro de Teoria da Computação, 2016)
No problema de centros dos p-terminais são dados um espaço métrico (V, d) e um conjunto D ⊆ V 2 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.