M Centres -

The objective of the m-centre problem is to minimize the maximum distance: [ \textMinimize \quad R(C) = \max_p_i \in P d(p_i, C) ]

| 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 | m centres

m-centre, minimax facility location, covering problems, NP-hard, computational geometry, location analysis. 1. Introduction In an increasingly networked world, the strategic placement of facilities—whether they are fire stations, distribution warehouses, or 5G base stations—directly impacts service quality, cost, and efficiency. A fundamental question arises: Given a region with demand points, where should we place m facilities to ensure the worst-case travel distance is as small as possible? The objective of the m-centre problem is to