Examining Heuristics for the K-Centers Problem - S. Shetty, Vikas; Mukherjee, Arka; Senthilkumar, K (International Journal of Engineering and Technology, 2018)
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.Â Â