Algoritmo aleatorizado basado en estructura para el problema de selección de k-centros (A Structure-driven Randomized Algorithm for the k-center Problem)

Jesus Garcia Diaz (jesgadiaz@gmail.com), Ricardo Menchaca Mendez (ric@cic.ipn.mx), Rolando Menchaca Mendez (rmen@cic.ipn.mx), Rolando Quintero (quintero@cic.ipn.mx)


Instituto Politécnico Nacional
This paper appears in: Revista IEEE América Latina

Publication Date: March 2015
Volume: 13,   Issue: 3 
ISSN: 1548-0992


Abstract:
In this paper we present a new randomized approximation algorithm for the metric discrete k-center problem. The main idea is to apply random perturbations to the decisions made by a deterministic approximation algorithm in such a way as to keep the approximation guarantees with high probability, but at the same time explore an extended neighborhood of the solutions produced by the deterministic approximation algorithm. We formally characterize the proposed algorithm and show that it produces 2-approximated solutions with probability of at least 1-1/N when it is repeated at least αlnN times. α,N∈Z^+ are user-defined parameters where α measures the size of the perturbations. Experimental results show that the proposed algorithm performs similar or better than a representative set of algorithms for the k-center problem and a GRASP algorithm, which is a popular state-of-the-art technique for randomizing deterministic algorithms. Our experiments also show that the quality of the solutions found by the proposed algorithm increases faster with the number of iterations and hence, is better suited for big instances where the execution of each iteration is very expensive.

Index Terms:
k-center selection problem, NP-Hard, randomized algorithms, approximation algorithms, GRASP   


Documents that cite this document
This function is not implemented yet.


[PDF Full-Text (473)]