[an error occurred while processing this directive]

Benchmarks:
UflLib

[an error occurred while processing this directive]

   UflLib

K-median Benchmarks

These are large scale benchmarks, which were translated from benchmarks for the k-median problem. They are similar to the instances in the Euclidian package. 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. The package can be downloaded here. An instance generator is also available.

References

[1] S. Ahn, C. Cooper, G. Cornuejols and A.M. Frieze
Probabilistic analysis of a relaxation for the k-median problem
Mathematics of Operations Research, 13:1-31, 1988.
[2] F. Barahona and F.A. Chudak
Near-optimal solutions to large scale facility location problems
Technical Report, IBM Watson Research Center, 2000.

 

[an error occurred while processing this directive]