M Centres _best_ Direct

The problem was introduced by Hakimi (1964) in the context of optimal locations on networks. Since then, it has evolved into a rich field intersecting graph theory, integer programming, and computational geometry.

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

This question defines the . Unlike the m-median problem, which minimizes total (average) distance, the m-centre problem is a minimax problem: it minimizes the maximum distance, thereby prioritizing equity and worst-case performance. This makes it particularly suitable for emergency services, where minimizing the response time for the most remote customer is a societal imperative. The problem was introduced by Hakimi (1964) in

Author: Academic Publishing Group Journal: Journal of Computational Operations Research Volume: 47, Issue 2 | Date: April 14, 2026 Abstract The m-centre problem (also known as the minimax facility location problem ) is a cornerstone of location science. Given a set of demand points (customers, cities, or incident locations), the objective is to locate ( m ) facilities (centres) such that the maximum distance between any demand point and its nearest facility is minimized. This paper provides a complete, self-contained treatment of the m-centre problem. We formally define the problem, classify its variants (vertex, absolute, and continuous), discuss its NP-hard nature, and present exact and heuristic solution methodologies, including the classic vertex substitution algorithm, binary search on distance with covering formulations, and the Shamos–Hoey computational geometry approach for the planar 1-centre. Finally, we explore real-world applications in emergency medical services (EMS), wireless network tower placement, and supply chain resilience. This question defines the

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

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) ]

Define the distance from a demand point ( p_i ) to its nearest centre as: [ d(p_i, C) = \min_c_j \in C d(p_i, c_j) ]