Paper by Erik D. Demaine
- 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.
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
Rd, find a size-k subset with minimum average
pairwise L1 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/(2d),
which is tight. We also give a polynomial-time
approximation scheme (PTAS) for constant dimension d
and report on experimental results.
- This paper is also available as arXiv:cs.DS/0407058 of the Computing Research Repository (CoRR), and from SpringerLink.
- The paper is \copyright Springer-Verlag.
- 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.
These pages are generated automagically from a
Last updated December 5, 2021 by