TY - JOUR
T1 - A Structure-driven Randomized Algorithm for the k-center Problem
AU - Garcia Diaz, Jesus
AU - Menchaca Mendez, Ricardo
AU - Menchaca Mendez, Rolando
AU - Quintero, Rolando
N1 - Publisher Copyright:
© 2003-2012 IEEE.
PY - 2015/3/1
Y1 - 2015/3/1
N2 - 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.
AB - 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.
KW - GRASP
KW - NP-Hard
KW - approximation algorithms
KW - k-center selection problem
KW - randomized algorithms
UR - http://www.scopus.com/inward/record.url?scp=84926636110&partnerID=8YFLogxK
U2 - 10.1109/TLA.2015.7069100
DO - 10.1109/TLA.2015.7069100
M3 - Artículo
SN - 1548-0992
VL - 13
SP - 746
EP - 752
JO - IEEE Latin America Transactions
JF - IEEE Latin America Transactions
IS - 3
M1 - 7069100
ER -