**Reference**:- Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, and Cynthia A. Phillips, “Communication-Aware Processor Allocation for Supercomputers”, in
*Proceedings of the 9th Workshop on Algorithms and Data Structures (WADS 2005)*, Lecture Notes in Computer Science, volume 3608, Waterloo, Ontario, Canada, August 15–17, 2005, pages 169–181. **Abstract**:-
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 7/4-approximation for 2D grids. In*d*dimensions, the approximation guarantee is 2 − 1/(2*d*), which is tight. We also give a polynomial-time approximation scheme (PTAS) for constant dimension*d*and report on experimental results. **Comments**:- This paper is also available as arXiv:cs.DS/0407058 of the Computing Research Repository (CoRR), and from SpringerLink.
**Copyright**:- The paper is \copyright Springer-Verlag.
**Availability**:- The paper is available in PostScript (459k), gzipped PostScript (181k), and PDF (182k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- MinAvgDistance_Algorithmica (Communication-Aware Processor Allocation for Supercomputers)
- MinAvgDistance_CCCG2009 (Integer Point Sets Minimizing Average Pairwise ℓ
_{1}Distance: What is the Optimal Shape of a Town?) - MinAvgDistance_JPhysA (What is the optimal shape of a city?)

See also other papers by Erik Demaine.

Last updated August 3, 2020 by Erik Demaine.