An n-town, n@?N, is a group of n buildings, each occupying a distinct position on a 2-dimensional integer grid. If we measure the distance between two buildings along the axis-parallel street grid, then an n-town has optimal shape if the sum of all pairwise Manhattan distances is minimized. This problem has been studied for cities, i.e., the limiting case of very large n. For cities, it is known that the optimal shape can be described by a differential equation, for which no closed-form solution is known. We show that optimal n-towns can be computed in O(n^7^.^5) time. This is also practically useful, as it allows us to compute optimal solutions up to n=80.
@cite_0: Abstract We consider the problem of placing a specified number ( p ) of facilities on the nodes of a network so as to minimize some measure of the distances between facilities. This type of problem models a number of problems arising in facility location, statistical clustering, pattern recognition, and processor allocation problems in multiprocessor systems. We consider the problem under three different objectives, namely minimizing the diameter, minimizing the average distance, and minimizing the variance. We observe that, in general, the problem is NP -hard under any of the objectives. Further, even obtaining a constant factor approximation for any of the objectives is NP -hard. We present a general framework for obtaining near-optimal solutions to the compact location problems for the above measures, when the distances satisfy the triangle inequality. We show that this framework can be extended to the case when there are also node weights. Further, we investigate the complexity and approximability of more general versions of these problems, where two distance values are specified for each pair of potential sites. In these cases, the goal is to a select a specified number of facilities to minimize a function of one distance metric subject to a budget constraint on the other distance metric. We present algorithms that provide solutions which are within a small constant factor of the objective value while violating the budget constraint by only a small constant factor.
@cite_14: We consider a facility location problem, where the objective is to “disperse” a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the average distance between selected locations is maximized. In particular, we present algorithmic results for the case where vertices are represented by points in d-dimensional space, and edge weights correspond to rectilinear distances. Problems of this type have been considered before, with the best result being an approximation algorithm with performance ratio 2. For the case where k is fixed, we establish a linear-time algorithm that finds an optimal solution. For the case where k is part of the input, we present a polynomial-time approximation scheme.
@cite_4: We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of communication hops. The associated clustering problem is as follows: Given n points in ℜ d, find a size-k subset with minimum average pairwise L 1 distance. We present a natural approximation algorithm and show that it is a @math -approximation for two-dimensional grids; in d dimensions, the approximation guarantee is @math , which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension d, and we report on experimental results.
@cite_0 consider the discrete problem of selecting a subset of @math nodes from a network with @math nodes to minimize their average pairwise distance. They prove a @math -approximation for metric distances and prove hardness of approximation for arbitrary distances. @cite_4 solve the geometric version of this problem, giving an efficient processor allocator for the Cplant setting described above, and a polynomial-time approximation scheme (PTAS) for minimizing the average Manhattan distance. For the reverse problem of maximizing the average Manhattan distance, see @cite_14 .