2004/07/24 by Michael A. Bender, David P. Bunde, Bender, Michael A. +12
Computer Science · #C.1.4 #Data Structures and Algorithms (cs.DS) #Distributed #Distributed and Parallel Computing Systems #F.2.2 #FOS: Computer and information sciences #Interconnection Networks and Systems #Parallel #Parallel Computing and Optimization Techniques #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.cs/0407058
19 pages, 7 figures, 1 table, Latex, submitted for journal publication. Previous version is extended abstract (14 pages), appeared in Proceedings WADS, Springer LNCS 3608, pp. 169-181
openalex publication_date 2004/07/24 · arxiv created 2005/12/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This paper gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures, in the presence of occupied cells. The simpler problem of assigning processors on a free grid has been studied by Karp, McKellar, and Wong who show that the solutions have nontrivial structure; they left open the complexity of the problem. The associated clustering problem is as follows: Given n points in Red, find k points that minimize their average pairwise L1 distance. We present a natural approximation algorithm and show that it is a 7/4-approximation for 2D grids. For d-dimensional space, 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.