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”, Algorithmica, volume 50, number 2, February 2008, pages 279–298. Special issue of selected papers from the 9th Workshop on Algorithms and Data Structures, 2005.
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 L1
distance. We present a natural approximation algorithm and show that it is a
7/4-approximation for two-dimensional 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 we report on experimental results.
- This paper is also available from SpringerLink.
- The paper is available in PDF (213k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- MinAvgDistance_WADS2005 (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 February 10, 2020 by