TY - JOUR
T1 - Local search algorithms for the vertex K-center problem
AU - Diaz, Jesus Garcia
AU - Mendez, Ricardo Menchaca
AU - Hernandez, Jairo Sanchez
AU - Mendez, Rolando Menchaca
N1 - Publisher Copyright:
© 2003-2012 IEEE.
PY - 2018/6
Y1 - 2018/6
N2 - The vertex k-center problem is a classical NP-Hard problem with applications to Clustering and Facility Location. It has been shown that this problem cannot be solved within a ρ&2 approximation factor, unless P=NP. Although there are approximation algorithms that achieve that 2-approximation factor, their performance on most benchmark instances is poor. Because of this, many useful heuristic and metaheuristic algorithms have been designed to address this problem. In this paper we evaluate the performance of a representative set of local search algorithms for the vertex k-center problem that includes a new local search algorithm that takes ideas from the Metropolis algorithm. Our experimental results show that the proposed algorithm outperforms some of the most representative local search algorithms from the literature, such as Tabu Search and the Metropolis algorithm itself. The reason for its good performance is that our proposal takes advantage of the flexibility of the Metropolis algorithm as well as of some specific properties of the vertex k-center problem.
AB - The vertex k-center problem is a classical NP-Hard problem with applications to Clustering and Facility Location. It has been shown that this problem cannot be solved within a ρ&2 approximation factor, unless P=NP. Although there are approximation algorithms that achieve that 2-approximation factor, their performance on most benchmark instances is poor. Because of this, many useful heuristic and metaheuristic algorithms have been designed to address this problem. In this paper we evaluate the performance of a representative set of local search algorithms for the vertex k-center problem that includes a new local search algorithm that takes ideas from the Metropolis algorithm. Our experimental results show that the proposed algorithm outperforms some of the most representative local search algorithms from the literature, such as Tabu Search and the Metropolis algorithm itself. The reason for its good performance is that our proposal takes advantage of the flexibility of the Metropolis algorithm as well as of some specific properties of the vertex k-center problem.
KW - Local search
KW - Metropolis
KW - Vertex k-center problem
UR - http://www.scopus.com/inward/record.url?scp=85052703260&partnerID=8YFLogxK
U2 - 10.1109/TLA.2018.8444397
DO - 10.1109/TLA.2018.8444397
M3 - Artículo
AN - SCOPUS:85052703260
SN - 1548-0992
VL - 16
SP - 1765
EP - 1771
JO - IEEE Latin America Transactions
JF - IEEE Latin America Transactions
IS - 6
M1 - 8444397
ER -