Paper by Erik D. Demaine

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”, 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.

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 ℝ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.

Comments:
This paper is also available from SpringerLink.

Availability:
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.