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 74-approximation for two-dimensional grids; in
d dimensions, the approximation guarantee is 2-12d, which is tight. We also give a …

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 R^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 74-approximation for 2D grids. In d
dimensions, the approximation guarantee is 2-12d, which is tight. We also give a polynomial …