78671

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

Favoritar este trabalho

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.