MAD Partitioning for Grid Graphs

For a graph facility or multi-facility location problem, each vertex is typically considered to be the location for one customer or one facility. Typically, the number of facilities is predetermined, and one must optimally locate these facilities so as to minimize some function of the distances between customers and facilities (and, perhaps, of the distances among the facilities). For example, p facility locations (such as, for hospitals or fire stations) might be chosen so as to minimize the maximum or the average distance from a customer to the nearest facility. The problem investigated in this paper considers all of the facilities to be distinct, and we seek to minimize the average customer-to-facility distance, primarily for grid graphs.