Examining Heuristics for the K-Centers Problem
Keywords:K-Centers, NP-Hard, Graph Theory, Facility Selection, Fast Machine Learning
In this paper, we discuss and analyze the heuristics existing to solve the K-Center problem. The K-Center problem is used in various practical scenarios such as facility location, load-balancing, ATM mapping, Cloud Server Selection, or even data clustering and image classification. Specifically, we examine a standard Greedy algorithm with an approximation factor of 2, the clustering algorithm introduced by Gonzales in 1985, and the Dominating Set Algorithm(commonly referred to as the elimination heuristic) devised by Jurij MiheliÄ and Borut RobiÄ. We also propose a new heuristic to solve the specified problem using Tree-Independent Dual-Trees devised by Ryan R. Curtin.
 M.S. DASKIN, â€œNetwork and Discrete Location: Models Algorithms and Applicationsâ€, Wiley, New York, 1995.
 CHARLES S. REVELLE AND H.A. EISELT, â€œLocation analysis: A synthesis and surveyâ€, European Journal of Operational Research, 165:1â€“19, 2005.
 JEFF ERICKSON, â€œK-Approximation Algorithms, Lecture Notes, Data Structures and Algorithmsâ€, University of Illinois at Urbanaâ€“Champaign, 2009
 T. GONZALEZ, â€œClustering to minimize the maximum intercluster distanceâ€, Theoretical Computer Science., 38:293â€“306, 1985.
 M.R. GAREY AND D.S. JOHNSON, â€œComputers and Intractability: A Guide to the Theory of NP-Completenessâ€, W.H. Freeman and Co., San Francisco, 1979.
 J. MIHELIÄŒ AND B. ROBIÄŒ, â€œApproximation algorithms for the k-center problem: an experimental evaluationâ€, Proc. OR 2002, Klagenfurt, Austria, 2002.
 J. MIHELI ÄŒ AND B. ROBIÄŒ, â€œSolving the k-center Problem Efficiently with a Dominating Set Algorithmâ€, Journal of Computing and Information Technology - CIT 13, 3, 225â€“233, 2005.
 D.S. HOCHBAUM, ed., â€œApproximation Algorithms for NP-hard Problemsâ€, PWS publishing company, Boston, 1995.
 "Introduction to Approximation Algorithms - K Center Problem", CSBreakdown(https://www.youtube.com/watch?v=dpYZojRuJEI)
 E. MINIEKA, â€œThe m-center problemâ€, SIAM Rev., 12:138â€“139, 1970.
 N.MLADENOVIÂ´C, M. LABBE, AND P. HANSEN, â€œSolving the p-center problem with tabu search and variable neighborhood searchâ€, Networks 42(1):48-64, 2003.
 S. ELLOUMI, M. LABBE, AND Y. POCHET, â€œNew formulation and resolution method for the p-center problemâ€, http://www.optimization-online.org/DB_HTM, 2001.
 T. ILHAN AND M.C. PINAR, â€œAn efficient exact algorithm for the vertex p-center problemâ€,http://www.optimization-online.org/DB_HTML/2001/10/376.html, 2001.
 RYAN R. CURTIN, WILLIAM B. MARCH, PARIKSHIT RAM, DAVID V. ANDERSON, ALEXANDER G. GRAY, CHARLES L. ISBELL, JR, â€œTree Independent Dual-Treesâ€, Proceedings of the 30 th International Conference on Machine Learning, Atlanta, Georgia, USA, 2013.
 Tomas Feder and Daniel H. Greene, â€œOptimal algorithms for approximate clusteringâ€, Proc. 20th STOC, 1988.
 Alikhani, S. and Peng, Y.-H, "Introduction to Domination Polynomial of a Graphâ€, Ars Combin. 114, 257-266, 2014.
 D.S. HOCHBAUM AND D.B. SHMOYS, "A best possible heuristic for the k-center problem" , Mathematics of Operations Research, 10:180â€“184, 1985.
 J. PLESNIK, â€œA Heuristic for the p-Center Problem in Graphsâ€, Discrete Applied Mathematics 17:263â€“268, 1987.
 V. VAZIRANI, â€œAproximation Algorithmsâ€, Springer, 2001
 Guha, S. & Khuller, S. Algorithmica (1998) 20: 374. https://doi.org/10.1007/PL00009201, 1998.
View Full Article:
How to Cite
LicenseAuthors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under aÂ Creative Commons Attribution Licensethat allows others to share the work with an acknowledgement of the work''s authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal''s published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (SeeÂ The Effect of Open Access).