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

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 ℓ₁ Distance: What is the Optimal Shape of a Town?)

MinAvgDistance_JPhysA (What is the optimal shape of a city?)