TY - JOUR
T1 - When a worse approximation factor gives better performance: a 3-approximation algorithm for the vertex k-center problem
T2 - a 3-approximation algorithm for the vertex k-center problem
AU - Garcia-Diaz, Jesus
AU - Sanchez-Hernandez, Jairo
AU - Menchaca-Mendez, Ricardo
AU - Menchaca-Mendez, Rolando
N1 - Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.
PY - 2017/7/1
Y1 - 2017/7/1
N2 - The vertex k-center selection problem is a well known NP-Hard minimization problem that can not be solved in polynomial time within a ρ< 2 approximation factor, unless P= NP. Even though there are algorithms that achieve this 2-approximation bound, they perform poorly on most benchmarks compared to some heuristic algorithms. This seems to happen because the 2-approximation algorithms take, at every step, very conservative decisions in order to keep the approximation guarantee. In this paper we propose an algorithm that exploits the same structural properties of the problem that the 2-approximation algorithms use, but in a more relaxed manner. Instead of taking the decision that guarantees a 2-approximation, our algorithm takes the best decision near the one that guarantees the 2-approximation. This results in an algorithm with a worse approximation factor (a 3-approximation), but that outperforms all the previously known approximation algorithms on the most well known benchmarks for the problem, namely, the pmed instances from OR-Lib (Beasly in J Oper Res Soc 41(11):1069–1072, 1990) and some instances from TSP-Lib (Reinelt in ORSA J Comput 3:376–384, 1991). However, the O(n4) running time of this algorithm becomes unpractical as the input grows. In order to improve its running time, we modified this algorithm obtaining a O(n2log n) heuristic that outperforms not only all the previously known approximation algorithms, but all the polynomial heuristics proposed up to date.
AB - The vertex k-center selection problem is a well known NP-Hard minimization problem that can not be solved in polynomial time within a ρ< 2 approximation factor, unless P= NP. Even though there are algorithms that achieve this 2-approximation bound, they perform poorly on most benchmarks compared to some heuristic algorithms. This seems to happen because the 2-approximation algorithms take, at every step, very conservative decisions in order to keep the approximation guarantee. In this paper we propose an algorithm that exploits the same structural properties of the problem that the 2-approximation algorithms use, but in a more relaxed manner. Instead of taking the decision that guarantees a 2-approximation, our algorithm takes the best decision near the one that guarantees the 2-approximation. This results in an algorithm with a worse approximation factor (a 3-approximation), but that outperforms all the previously known approximation algorithms on the most well known benchmarks for the problem, namely, the pmed instances from OR-Lib (Beasly in J Oper Res Soc 41(11):1069–1072, 1990) and some instances from TSP-Lib (Reinelt in ORSA J Comput 3:376–384, 1991). However, the O(n4) running time of this algorithm becomes unpractical as the input grows. In order to improve its running time, we modified this algorithm obtaining a O(n2log n) heuristic that outperforms not only all the previously known approximation algorithms, but all the polynomial heuristics proposed up to date.
KW - Approximation algorithm
KW - Dominating set
KW - k-Center problem
KW - Polynomial time heuristic
UR - http://www.scopus.com/inward/record.url?scp=85021696158&partnerID=8YFLogxK
U2 - 10.1007/s10732-017-9345-x
DO - 10.1007/s10732-017-9345-x
M3 - Artículo
AN - SCOPUS:85021696158
SN - 1381-1231
VL - 23
SP - 349
EP - 366
JO - Journal of Heuristics
JF - Journal of Heuristics
IS - 5
ER -