A generalized Weiszfeld algorithm for the multi-facility location

problem, with applications to data analysis

Adi Ben-Israel

Abstract: Given N customers (as coordinates), their demands, and the

number K of facilities, the method uses probabilistic assignments of customers

to facilities, with probabilities that are assumed inversely proportional

to distances. The extremum problem corresponding to this assumption is

solved iteratively in what is a generalized Weiszfeld algorithm.

The algorithm provides natural criteria for the goodness of data

approximation, and for the uncertainty of classification. It is easily

adapted to the capacitated case.

Applications include:

(a) clustering,

(b) classification,

(c) density estimation,

(d) contour approximation of data,

(e) the ``right'' number of clusters, and

(f) Voronoi diagrams.

Joint work with Cem Iyigun.

References

[1] A. B-I and C. Iyigun, Probabilistic distance clustering, J.

Classification 25(2008), 5-26

[2] C. Iyigun and A. B-I, Probabilistic distance clustering adjusted for

cluster size, Probability in Engrg and Info. Sci. 22(2008), 1-19