El problema de los proveedores capacitados con menor suma de radios en la línea

Abstract

El presente trabajo estudia un problema de asignación de clientes a centros de atención: dado un conjunto de clientes en un grafo métrico, y un conjunto de centros en los cuales hay servidores disponibles, se desea asignar a cada cliente su centro de atención, de manera de minimizar el tiempo que toma a los servidores de cada punto atender a los clientes asignados. Distintas restricciones y formas de medir el tiempo de atención de los servidores definen tres variantes: makespan, soft-capacidades y hard-capacidades. Se estudia la relación que tienen estas variantes entre sí: en particular, la variante makespan se reduce (perdiendo un factor de 3/2) a la variante con soft-capacidades. Posteriormente el estudio se concentra en un tipo particular de instancia, la línea, para la cual se detalla un algoritmo exacto para la variante con soft-capacidades, y una 2-aproximación para la variante con hard-capacidades.