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. |