Examining Heuristics for the K-Centers Problem

  • Authors

    • Vikas S. Shetty
    • Arka Mukherjee
    • K Senthilkumar
    2018-07-20
    https://doi.org/10.14419/ijet.v7i3.12.16560
  • 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.

     

     

  • References

    1. [1] M.S. DASKIN, “Network and Discrete Location: Models Algorithms and Applicationsâ€, Wiley, New York, 1995.

      [2] CHARLES S. REVELLE AND H.A. EISELT, “Location analysis: A synthesis and surveyâ€, European Journal of Operational Research, 165:1–19, 2005.

      [3] JEFF ERICKSON, “K-Approximation Algorithms, Lecture Notes, Data Structures and Algorithmsâ€, University of Illinois at Urbana–Champaign, 2009

      [4] T. GONZALEZ, “Clustering to minimize the maximum intercluster distanceâ€, Theoretical Computer Science., 38:293–306, 1985.

      [5] 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.

      [6] J. MIHELIÄŒ AND B. ROBIÄŒ, “Approximation algorithms for the k-center problem: an experimental evaluationâ€, Proc. OR 2002, Klagenfurt, Austria, 2002.

      [7] 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.

      [8] D.S. HOCHBAUM, ed., “Approximation Algorithms for NP-hard Problemsâ€, PWS publishing company, Boston, 1995.

      [9] "Introduction to Approximation Algorithms - K Center Problem", CSBreakdown(https://www.youtube.com/watch?v=dpYZojRuJEI)

      [10] E. MINIEKA, “The m-center problemâ€, SIAM Rev., 12:138–139, 1970.

      [11] 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.

      [12] 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.

      [13] 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.

      [14] 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.

      [15] Tomas Feder and Daniel H. Greene, “Optimal algorithms for approximate clusteringâ€, Proc. 20th STOC, 1988.

      [16] Alikhani, S. and Peng, Y.-H, "Introduction to Domination Polynomial of a Graphâ€, Ars Combin. 114, 257-266, 2014.

      [17] D.S. HOCHBAUM AND D.B. SHMOYS, "A best possible heuristic for the k-center problem" , Mathematics of Operations Research, 10:180–184, 1985.

      [18] J. PLESNIK, “A Heuristic for the p-Center Problem in Graphsâ€, Discrete Applied Mathematics 17:263–268, 1987.

      [19] V. VAZIRANI, “Aproximation Algorithmsâ€, Springer, 2001

      [20] Guha, S. & Khuller, S. Algorithmica (1998) 20: 374. https://doi.org/10.1007/PL00009201, 1998.

  • Downloads

  • How to Cite

    S. Shetty, V., Mukherjee, A., & Senthilkumar, K. (2018). Examining Heuristics for the K-Centers Problem. International Journal of Engineering & Technology, 7(3.12), 915-918. https://doi.org/10.14419/ijet.v7i3.12.16560