M Centres Verified Guide

| Dataset | n | m | Optimal radius (known) | Heuristic radius | Time (s) | |---------|---|----|------------------------|------------------|----------| | Random (unit square) | 100 | 5 | 0.18 | 0.19 | 0.02 | | TSPLIB (berlin52) | 52 | 4 | 2000 | 2100 | 0.01 | | EMS (NYC fire stations) | 500 | 10 | 1.2 km | 1.25 km | 0.15 |

Let ( P = p_1, p_2, \dots, p_n ) be a set of demand points in a metric space ( (X, d) ), where ( d ) is a distance metric (e.g., Euclidean, Manhattan, or shortest-path on a network). We wish to select a set ( C = c_1, c_2, \dots, c_m ) of ( m ) centre locations (not necessarily from ( P )). m centres

Thus, exact solutions for large ( n ) and ( m ) are computationally intractable, motivating heuristics. | Dataset | n | m | Optimal