14 citations · 22 across the 5 of their papers we have counts for
5 papers · 1 filter
Communication-Aware Processor Allocation for Supercomputers
Michael A. Bender, David P. Bunde, Erik D. Demaine +4
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…
Insertion Sort is O(n log n)
Michael A. Bender, Martin Farach-Colton, Miguel Mosteiro
Traditional Insertion Sort runs in O(n^2) time because each insertion takes O(n) time. When people run Insertion Sort in the physical world, they leave gaps between items to accele…
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots
Esther M. Arkin, Michael A. Bender, Sandor P. Fekete +2
An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of ``asleep'' robots, by having an awakened robo…
Optimal Covering Tours with Turn Costs
Esther M. Arkin, Michael A. Bender, Erik D. Demaine +3
We give the first algorithmic study of a class of ``covering tour'' problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it swee…
Efficient Tree Layout in a Multilevel Memory Hierarchy
Stephen Alstrup, Michael A. Bender, Erik D. Demaine +3
We consider the problem of laying out a tree with fixed parent/child structure in hierarchical memory. The goal is to minimize the expected number of block transfers performed duri…