1: Abstract:

From many decades, there

are large numbers of searches which are made on facility problems. The k-center

problem is a very common problem in public or private sector. There are many

efforts which have been made for optimal solution of this nature problem. The

point of this paper is to draw an attention on algorithmic approach which has

been in that area. In future, new researches on this topic will be made.

2: Introduction:

K center algorithms (greedy

algorithms) are a way to make a summarized connection from an origin to a

destiny. It is like centralized a destiny from certain points, that the point

can get benefit from it. Facility location problem is a very well known

problem, suppose the given no. of cities and distances between cities, we want

to choose k cities which is also called center. In that case we minimized the

distance between center and the largest distance city.

Figure 1:

As we can see that {4,3,10,11,13} are the five point that we

pick from {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} , the five points we picked are

the centralized points , through all the other points can b interact easily and

have short path to get the needy things.

3:

Literature review:

In computer science and operation research literature,

k-center problem got highly attention. Hockbaum and Shmoys (1985) proposed 2

approximate algorithms of k center problem with triangle inequality.

After Hocbaum and Shmoys, J Plesnik in 1987 gathered

the results, with the worst case error ratio of 2 is developed for p center

problem.

After that Daskin modified those algorithms of p

center problem to find optimal solution. He also presents a new model for k

center problem in 2000.

In 2005 Al Khedhairi modified those old algorithms

to solve the k center problem, he speed up that process of solving the k center

problem.

4:

Methodology (Explanation of algorithm):

GreedyKCenter(P, k) {

G = empty

for each u in P do // initialize distances

du = INFINITY

for (i = 1 to k) {

Let u be the point of P such that du is maximum

Add u to G // u is the next cluster center

for (each v in P) { // update distance to nearest

center

dv = min(dv, distance(v,u))

}

Delta = max_{v in P} dv // update the bottleneck

distance

}

return (G, Delta) // final centers and max distance

}

Figure 2:

As we can see that, from the center point we draw a

line which is called radius, through this we made circumference, and that

circumference cover the near points, that center is like a warehouse, and the

other points the things that they need. The circumference that we made contain

the points that have smallest path from the center, and easy to cover the

distance.

5: Analysis and Comparison with other algo’s solving same

problem:

6: Major finding: