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 BibTeX file.
Last updated March 12, 2024 by Erik Demaine.