M Centres May 2026

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?

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) ] 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. A fundamental question arises: Given a region with