Anticipatory Bound Selection Procedure (ABSP) for Vertex K-Center Problem

Rattan Ran and Deepak Garg
Computer Science and Engineering Department, Thapar University, India

Abstract: Vertex k-center problem introduces the notion to recognize k locations as centers in a given network of n connected nodes holding the condition of triangle inequality. This paper presents an efficient algorithm that provides a better solution for vertex k-center problem. Anticipatory Bound Selection Procedure (ABSP) is deployed to find the initial threshold distance (or radius) and eradicating the gap between minimum distance (lower bound) and maximum distance (upper bound). The jump based scheme is applied to find the optimal coverage distance. Main aspect of this algorithm is to provide optimal solution with less iteration which has not been achieved so far.

Keywords: Facility planning and design, facility location allocation, k-center, set covering problem.

 

 

Full Text