26 citations · 54 across the 9 of their papers we have counts for
5 papers · 1 filter
Logarithmic Lower Bounds in the Cell-Probe Model
Mihai Patrascu, Erik D. Demaine
We develop a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized Omega(lg n) lower bound per op…
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…
Online Searching with Turn Cost
Erik D. Demaine, Sandor P. Fekete, Shmuel Gal
We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the…
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…