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: Finding Point Sets of Small Average Distance”, 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.

BibTeX

@Article{MinAvgDistance_Algorithmica,
  AUTHOR        = {Michael A. Bender and David P. Bunde and Erik D. Demaine and
                   S{\'a}ndor P. Fekete and Vitus J. Leung and Henk Meijer and
                   Cynthia A. Phillips},
  TITLE         = {Communication-Aware Processor Allocation for Supercomputers: Finding Point Sets of Small Average Distance},
  JOURNAL       = {Algorithmica},
  journalurl    = {https://www.springer.com/journal/453},
  VOLUME        = 50,
  NUMBER        = 2,
  MONTH         = {February},
  YEAR          = 2008,
  PAGES         = {279--298},
  NOTE          = {Special issue of selected papers from the 9th Workshop on
                   Algorithms and Data Structures, 2005.},

  doi           = {https://dx.doi.org/10.1007/s00453-007-9037-2},
  dblp          = {https://dblp.org/rec/journals/algorithmica/BenderBDFLMP08},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/s00453-007-9037-2">SpringerLink</A> and as <A HREF="https://arXiv.org/abs/cs.DS/0407058">arXiv:cs.DS/0407058</A>.},
  replaces      = {MinAvgDistance_WADS2005},
  papers        = {MinAvgDistance_WADS2005; MinAvgDistance_CCCG2009; MinAvgDistance_JPhysA},
}

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 L₁ 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 and as arXiv:cs.DS/0407058.

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

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