Algoritmo aleatorizado basado en estructura para el problema de selección de kcentros
(A Structuredriven Randomized Algorithm for the kcenter 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: 15480992
Abstract:
In this paper we present a new randomized approximation algorithm for the metric discrete kcenter 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 2approximated solutions with probability of at least 11/N when it is repeated at least αlnN times. α,N∈Z^+ are userdefined 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 kcenter problem and a GRASP algorithm, which is a popular stateoftheart 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:
kcenter selection problem, NPHard, randomized algorithms, approximation algorithms, GRASP
Documents that cite this
document
This function is not implemented yet.
[PDF FullText (473)]
