This is an archived website. The group moved to RWTH Aachen University.

UflLib


K-Median Instances

Similar instances: Euclidian

These are large scale benchmarks, which were translated from benchmarks for the k-median problem. In the Euclidian plane n points are generated. Each point is simultaneously facility and customer (m = n). The connection costs are determined by the Euclidian distance. All the opening costs are equal and calculated by one of the following formulas:

Type Opening cost

I

sqrt(n) / 10

II

sqrt(n) / 100

III

sqrt(n) / 1000


We generated 6 problems of Type I with m = n = 500, 1000, 1500, 2000, 2500, 3000. We also included code for a little program that allows the user to adjust the opening costs. To prevent rounding errors, we rounded all data up to 4 significant digits and then made all the entries integer.


References

[1] S. Ahn, C. Cooper, G. Cornuejols, A. Frieze
Probabilistic analysis of a relaxation for the k-median problem.
Mathematics of Operations Research 13:1-31, 1988.
[2] F. Barahona, F. Chudak
Near-optimal solutions to large scale facility location problems.
Discrete Optimization 2(1):35-50, 2005.