Voltar
Artigo Acesso aberto Produção Nacional
BIBTEX RIS

Algoritmos de Aproximação para o Problema de Alocação de p-Terminais e Variantes

2017; Linguagem: Inglês

10.19146/pibic-2017-78671

ISSN

2447-5114

Autores

Vinícius Balbino de Souza, Lehilton L. C. Pedrosa,

Tópico(s)

Academic Research in Diverse Fields

Resumo

We consider the Capacitated p-Hub Center Problem.An instance comprises a metric space V, a set of demands D V²,a number of hubs p, and a capacity L. A solution is a multiset S of locations where to install hubs with |S| ≤ p and ⊆ an assignment from each demand to a hub such that no hub receives more than L demands.The objective is to find a solution that minimizes the maximum cost of serving a demand through the assigned hub.In this work, we give the first approximation algorithm for the problem, that achieves factor 7.

Referência(s)