  This paper gives processor-allocation algorithms for minimizing the average
number of communication hops between the assigned processors for grid
architectures, in the presence of occupied cells. The simpler problem of
assigning processors on a free grid has been studied by Karp, McKellar, and
Wong who show that the solutions have nontrivial structure; they left open the
complexity of the problem.
  The associated clustering problem is as follows: Given n points in Re^d, find
k points that minimize their average pairwise L1 distance. We present a natural
approximation algorithm and show that it is a 7/4-approximation for 2D grids.
For d-dimensional space, the approximation guarantee is 2-(1/2d), which is
tight. We also give a polynomial-time approximation scheme (PTAS) for constant
dimension d, and report on experimental results.
