(1) Computer Science Department
Instituto Nacional de Astrofísica, Óptica y Electrónica, Mexico
(2) Graduate Program in Systems Engineering
Universidad Autónoma de Nuevo León, Mexico
Abstract: The uniform capacitated vertex k-center problem is an NP-hard combinatorial optimization problem that models real situations where k centers can only attend a maximum number of customers, and the travel time or distance from the customers to their assigned center has to be minimized. This paper introduces a polynomial-time constructive heuristic algorithm that exploits the relationship between this problem and the minimum capacitated dominating set problem. The proposed heuristic is based on the one-hop farthest-first heuristic that has proven effective for the uncapacitated version of the problem. We carried out different empirical evaluations of the proposed heuristics, including an analysis on the effect of a parallel implementation of the algorithm, which significantly improved the running time for relatively large instances.