Optimal covering tours with turn costs (2009)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, S Ándor, P. Fekete, ...
Abstract. 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 sweeps out...
Contention Resolution with Heterogeneous Job Sizes (2009)
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert
Abstract. We study the problem of contention resolution for differentsized jobs on a simple channel. When a job makes a run attempt, it learns only whether the attempt succeeded or failed. We first...
Contention Resolution with Heterogeneous Job Sizes (2009)
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert
Abstract. We study the problem of contention resolution for differentsized jobs on a simple channel. When a job makes a run attempt, it learns only whether the attempt succeeded or failed. We first...
The Worst Page-Replacement Policy (2009)
Kunal Agrawal, Michael A. Bender, Jeremy T. Fineman
Abstract. In this paper, we consider the question: what is the worst possible page-replacement strategy? Our goal is to devise an online strategy that has the highest possible fraction of misses as...
ABSTRACT Cache-Oblivious Streaming B-trees (2008)
Michael A. Bender, Yonatan R. Fogel, Martin Farach-colton, Bradley C. Kuszmaul
A streaming B-tree is a dictionary that efficiently implements insertions and range queries. We present two cache-oblivious streaming B-trees, the shuttle tree, and the cache-oblivious lookahead...
ABSTRACT Concurrent Cache-Oblivious B-Trees (2008)
Michael A. Bender, Seth Gilbert
This paper presents concurrent cache-oblivious (CO) B-trees. We extend the cache-oblivious model to a parallel or distributed setting and present three concurrent CO B-trees. Our first data structure...
Optimal Covering Tours with Turn Costs Esther M. Arkin \Lambda (2008)
Michael A. Bender, Erik D. Demaine
S'andor P. Fekete x Joseph S. B. Mitchell \Lambda Saurabh Sethia
The Worst Page-Replacement Policy (2008)
Kunal Agrawal, Michael A. Bender, Jeremy T. Fineman
Abstract. In this paper, we consider the question: what is the worst possible page-replacement strategy? Our goal is to devise an online strategy that has the highest possible fraction of misses as...
Yonatan Aumann, Michael A. Bender
Abstract. We consider asynchronous consensus in the shared-memory setting. We present the first efficient lowcontention consensus algorithm for the weak-adversaryscheduler model. The algorithm...
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-colton, Jack Zito Two
Advanced topics in data structures: bibliography list on string matching
ABSTRACT Cache-Oblivious Streaming B-trees (2008)
Michael A. Bender, Yonatan R. Fogel, Martin Farach-colton, Bradley C. Kuszmaul
A streaming B-tree is a dictionary that efficiently implements insertions and range queries. We present two cache-oblivious streaming B-trees, the shuttle tree, and the cache-oblivious lookahead...
Yonatan Aumann, Michael A. Bender
We study the tolerance of data structures to memory faults. We observe that many pointerbased data structures (e.g., linked lists, trees, etc.) are highly nonresilient to faults. A single fault in a...
Contention Resolution with Heterogeneous Job Sizes (2008)
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert
Abstract. We study the problem of contention resolution for differentsized jobs on a simple channel. When a job makes a run attempt, it learns only whether the attempt succeeded or failed. We first...
ABSTRACT Concurrent Cache-Oblivious B-Trees (2008)
Michael A. Bender, Seth Gilbert
This paper presents concurrent cache-oblivious (CO) B-trees. We extend the cache-oblivious model to a parallel or distributed setting and present three concurrent CO B-trees. Our first data structure...
Improved Bounds on Sorting by Length-Weighted Reversals ∗ (2008)
Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, ...
We study the problem of sorting binary sequences and permutations by length-weighted reversals. We consider a wide class of cost functions, namely f(ℓ) = ℓ α for all α ≥ 0, where ℓ is the...
The Worst Page-Replacement Policy (2008)
Kunal Agrawal, Michael A. Bender, Jeremy T. Fineman
Abstract. In this paper, we consider the question: what is the worst possible page-replacement strategy? Our goal is to devise an online strategy that has the highest possible fraction of misses as...
Adversarial Analyses of Window Backoff Strategies for Simple Multiple-Access Channels (2008)
Michael A. Bender, Martin Farach-colton, Simai He, Bradley C. Kuszmaul, Charles E. Leiserson
Abstract — Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the...
ABSTRACT Improved Approximation Algorithms for the Freeze-Tag Problem (2008)
Esther M. Arkin, Simai He, Michael A. Bender, Dongdong Ge
In the Freeze-Tag Problem, the objective is to awaken a set of “asleep ” robots, starting with only one “awake ” robot. A robot awakens a sleeping robot by moving to the sleeping robot’s...
ABSTRACT Concurrent Cache-Oblivious B-Trees (2008)
Michael A. Bender, Seth Gilbert
This paper presents concurrent cache-oblivious (CO) B-trees. We extend the cache-oblivious model to a parallel or distributed setting and present three concurrent CO B-trees. Our first data structure...
Contention Resolution with Heterogeneous Job Sizes (2008)
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert
Abstract. We study the problem of contention resolution for differentsized jobs on a simple channel. When a job makes a run attempt, it learns only whether the attempt succeeded or failed. We first...
Michael A. Bender, Riko Jacob, Elias Vicari
We analyze the problem of sparse-matrix dense-vector multiplication (SpMV) in the I/O-model. The task of SpMV is to compute y: = Ax, where A is a sparse N × N matrix and x and y are vectors. Here,...
ABSTRACT Cache-Oblivious String B-trees (2008)
Michael A. Bender, Martin Farach-colton, Bradley C. Kuszmaul
B-trees are the data structure of choice for maintaining searchable data on disk. However, B-trees perform suboptimally • when keys are long or of variable length, • when keys are compressed,...
ABSTRACT Concurrent Cache-Oblivious B-Trees (2008)
Michael A. Bender, Seth Gilbert
This paper presents concurrent cache-oblivious (CO) B-trees. We extend the cache-oblivious model to a parallel or distributed setting and present three concurrent CO B-trees. Our first data structure...
INSERTION SORT is O(n log n) ∗ (2008)
Michael A. Bender, Martín 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 accelerate insertions....
Scheduling Algorithms for Procrastinators (2008)
Michael A. Bender, Raphaël Clifford, Kostas Tsichlas
If once a man indulges himself in murder, very soon he comes to think little of robbing; and from robbing he comes next to drinking and Sabbath-breaking, and from that to incivility and...
The sum-of-squares algorithm (SS) was introduced by Csirik, Johnson, Kenyon, Shor, and Weber for online bin packing of integral-sized items into integral-sized bins. First, we show the results of...
ABSTRACT Concurrent Cache-Oblivious B-Trees (2008)
Michael A. Bender, Seth Gilbert
This paper presents concurrent cache-oblivious (CO) B-trees. We extend the cache-oblivious model to a parallel or distributed setting and present three concurrent CO B-trees. Our first data structure...
Abotract The Power of a Pebble: Exploring and Mapping Directed Graphs (2008)
Michael A. Bender, Antonio Fernfindezt, Dana Ron, Amit Salil Vadhana
Exploring and mapping an unknown environment is a fun-damcntal problem that is studied in a variety of contexts. Many works have focused on finding efficient solutions to re-atrictcd versions of the...
An Adaptive Packed-Memory Array (2008)
The packed-memory array (PMA) is a data structure that maintains a dynamic set of N elements in sorted order in a Θ(N)-sized array. The idea is to intersperse Θ(N) empty spaces or gaps among the...
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Charles E. Leiserson
A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two...
Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Martin Skutella
Abstract. 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 robot move...
ABSTRACT Concurrent Cache-Oblivious B-Trees (2008)
Michael A. Bender, Seth Gilbert
This paper presents concurrent cache-oblivious (CO) B-trees. We extend the cache-oblivious model to a parallel or distributed setting and present three concurrent CO B-trees. Our first data structure...
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Charles E. Leiserson
A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two...
INSERTION SORT is O(n log n) (2008)
Michael Bender Mart, Michael A. Bender, Martín Farach-colton, Miguel A. Mosteiro
Traditional INSERTION SORT runs in O(n ) time because each insertion takes O(n) time. When people run INSERTION SORT in the physical world, they leave gaps between items to accelerate insertions.
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia
S. Skiena y The easiest way to refold a road map is differently.--- Jones's Rule of the Road (M. Gardner [3]) 1
Michael A. Bender, Erik D. Demaine, Martin Farach-colton
We present dynamic search-tree data structures that perform well in the setting of a hierarchical memory (including various levels of cache, disk, etc.), but do not depend on the number of memory...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Lars Arge, Michael A. Bender, Erik D. Demaine, J. Ian Munro
In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O( 1 B log M=B
Yonatan Aumann, Michael A. Bender, Lisa Zhang
We consider the problem of asynchronous execution of parallel programs. We assume that the original program is designed for a synchronous system, whereas the actual system may be asynchronous. We...
Michael A. Bender, Antonio Fernandez, Dana Ron, Amit Sahai, Salil Vadhan
Abstract. Exploring and mapping an unknown environment is a fundamental problem, which is studied in various contexts. Many works have focused on finding efficient solutions to restricted versions of...
Michael A. Bender, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin
We study the problem of nding least common ancestors (LCA) in trees and directed acyclic graphs (DAGs). We present a very simple optimal algorithm for the LCA problem in trees. We thus dispel the...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Data Structures for Maintaining Set Partitions (Extended Abstract) (2007)
Michael A. Bender, Saurabh Sethia, Steven Skiena
Each test or feature in a classication system denes a set partition on a class of objects. Adding new features renes the classication, whereas deleting features may result in merging previously...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Saurabh Sethia
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 sweeps...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Saurabh Sethia
We give the rst 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 sweeps out a...
New Algorithms for Disk Scheduling (2007)
Matthew Andrews, Michael A. Bender, Lisa Zhang
Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/O performance could become an important bottleneck. Methods are needed for...
When Can You Fold a Map? (2007)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
The Level Ancestor Problem Simpli (2007)
Ed Michael Bender, Michael A. Bender
We present a very simple algorithm for the Level Ancestor Problem. A Level Ancestor Query LA(v; d) requests the depth d ancestor of node v. The Level Ancestor Problem is thus: preprocess a given...
When Can You Fold a Map? (2007)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Online Dispersion Algorithms for Swarms of Robots (2007)
Tien-ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sándor P. Fekete
We illustrate algorithms for dispersing a swarm of primitive robots in a two-dimensional unknown environment R. Each robot in the swarm is equipped with a very simple sensor that is able to query the...
When Can You Fold a Map? (2007)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a at folding by a sequence of simple folds?...
Optimal Cache-Oblivious Mesh Layouts (2007)
Bender, Michael A., Kuszmaul, Bradley C., Teng, Shang-Hua, Wang, Kebin
This paper shows how to generate a cache-oblivious memory layout of a well-shaped finite-element mesh G. This cache-oblivious mesh layout enables asymptotically optimal mesh updates, in which each...
Optimal Shape of a Blob (2007)
Bender, Carl M., Bender, Michael A.
This paper presents the solution to the following optimization problem: What is the shape of the two-dimensional region that minimizes the average L_p distance between all pairs of points if the area...
An Optimal Cache-Oblivious Priority Queue and its Application to Graph Algorithms (2007)
Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro
We develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and delete-min operations in $O(\frac{1}{B}\log_{M/B}\frac{N}{B})$ amortized memory transfers,...
Carl M. Bender, Michael A. Bender
This paper presents the solution to the following optimization problem: What is the shape of the two-dimensional region that minimizes the average Lp distance between all pairs of points if the area...
Scheduling Algorithms for Procrastinators (2006)
Bender, Michael A., Clifford, Raphael, Tsichlas, Kostas
This paper presents scheduling algorithms for procrastinators, where the speed that a procrastinator executes a job increases as the due date approaches. We give optimal off-line scheduling policies...
Arkin, Esther M., Bender, Michael A., Mitchell, Joseph S. B., Polishchuk, Valentin
We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to compute a...
Esther M. Arkin, Michael A. Bender
Abstract: We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to...
Esther M. Arkin, Michael A. Bender
Abstract: We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to...
Accepted to SIAM Journal on Computing (2006)
Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holl
We develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and delete-min operations in O ( 1 B logM/B N B) amortized memory transfers, where M and B are the...
Esther M. Arkin, Michael A. Bender
Abstract: We introduce the snowblower problem (SBP), a new optimization problem that is closely related to milling problems and to some material-handling problems. The objective in the SBP is to...
Optimal Shape of a Blob (2005)
Carl M. Bender, Michael A. Bender
This paper presents the solution to the following optimization problem: What is the shape of the region that minimizes the average Lp distance between all pairs of points if the area of this region...
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Or P. Fekete, Vitus J. Leung, Henk Meijer, ...
1
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, ...
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...
Efficient Low-Contention Asynchronous Consensus with the Value-Oblivious Adversary Scheduler (2005)
Yonatan Aumann, Yonatan Aumann, Michael A. Bender, Michael A. Bender
We consider asynchronous consensus in the shared memory setting. We present the first efficient low-contention consensus algorithm for the weak adversary scheduler model. The algorithm achieves...
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, ...
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...
Adversarial contention resolution for simple channels (2005)
Michael A. Bender, Bradley C. Kuszmaul
This paper analyzes the worst-case performance of randomized backoff on simple multiple-access channels. Most previous analysis of backoff has assumed a statistical arrival model. For batched...
Lowest common ancestors in trees and directed acyclic graphs (2005)
Michael A. Bender, Martín Farach-colton, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin
We study the problem of finding lowest common ancestors (LCA) in trees and directed acyclic graphs (DAGs). Specifically, we extend the LCA problem to DAGs and study the LCA variants that arise in...
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, ...
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...
04301 Abstracts Collection -- Cache-Oblivious and Cache-Aware Algorithms (2005)
Arge, Lars, Bender, Michael A., Demaine, Erik, Leiserson, Charles, Mehlhorn, Kurt
The Dagstuhl Seminar 04301 ``Cache-Oblivious and Cache-Aware Algorithms'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl, from 18.07.2004 to 23.07.2004. During...
On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs (2004)
Bender, Michael A., Fineman, Jeremy T., Gilbert, Seth, Leiserson, Charles E.
A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two...
On-the-Fly Maintenance of Series-Parallel Relationships in Fork-Join Multithreaded Programs (2004)
Bender, Michael A., Fineman, Jeremy T., Gilbert, Seth, Leiserson, Charles E.
A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two...
Communication-Aware Processor Allocation for Supercomputers (2004)
Bender, Michael A., Bunde, David P., Demaine, Erik D., Fekete, Sandor P., Leung, Vitus J., Meijer, Henk, ...
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...
Insertion Sort is O(n log n) (2004)
Bender, Michael A., Farach-Colton, Martin, Mosteiro, Miguel
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 accelerate insertions....
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (2004)
Arkin, Esther M., Bender, Michael A., Fekete, Sandor P., Mitchell, Joseph S. B., Skutella, Martin
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 robot move to their...
Sorting by length-weighted reversals: Dealing with signs and circularity (2004)
Firas Swidan, Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter
Abstract. We consider the problem of sorting linear and circular permutations and 0/1 sequences by reversals in a length-sensitive cost model. We extend the results on sorting by length-weighted...
On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs (2004)
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Charles E. Leiserson
A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two...
Improved Bounds on Sorting with Length-Weighted Reversals (Extended Abstract) (2004)
Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, ...
Michael A. Bender y Dongdong Ge Simai He Haodong Hu Ron Y. Pinter Steven Skiena Firas Swidan Abstract We study the problem of sorting integer sequences and permutations by length-weighted reversals....
Communication-Aware Processor Allocation for Supercomputers (2004)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sandor P. Fekete, Vitus J. Leung, Henk Meijer, ...
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...
Sorting by length-weighted reversals: Dealing with signs and circularity (2004)
Firas Swidan, Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter
Abstract. We consider the problem of sorting linear and circular permutations and 0/1 sequences by reversals in a length-sensitive cost model. We extend the results on sorting by length-weighted...
INSERTION SORT is O(n log n) (2004)
Michael A. Bender, Martín Farach-Colton, Miguel Mosteiro
Traditional INSERTION SORT runs in O(n²) time because each insertion takes O(n) time. When people run INSERTION SORT in the physical world, they leave gaps between items to accelerate...
On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs (2004)
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Charles E. Leiserson
A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two...
Michael A. Bender, Jeremy T. Fineman, Seth Gilbert, Charles E. Leiserson
A key capability of data-race detectors is to determine whether one thread executes logically in parallel with another or whether the threads must operate in series. This paper provides two...
Adversarial Analyses of Window Backoff Strategies for Simple Multiple-Access Channels (2003)
Bender, Michael A., Farach-Colton, Martin, He, Simai, Kuszmaul, Bradley C., Leiserson, Charles E.
Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the efficacy of...
Adversarial Analyses of Window Backoff Strategies for Simple Multiple-Access Channels (2003)
Bender, Michael A., Farach-Colton, Martin, He, Simai, Kuszmaul, Bradley C., Leiserson, Charles E.
Backoff strategies have typically been analyzed by making statistical assumptions on the distribution of problem inputs. Although these analyses have provided valuable insights into the efficacy of...
Optimal Covering Tours with Turn Costs (2003)
Arkin, Esther M., Bender, Michael A., Demaine, Erik D., Fekete, Sandor P., Mitchell, Joseph S. B., Sethia, Saurabh
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 sweeps out a specified...
Improved approximation algorithms for the freeze-tag problem (2003)
Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai Hejoseph, S. B. Mitchell
Abstract The following scheduling problem naturally arises in thestudy of swarm robotics. Consider a set of n robots, mod-eled as points in some metric space (e.g., vertices of an edge-weighted...
What is the Optimal Shape of a City? (2003)
Carl M. Bender, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete
If one de nes the distance between two points as the Manhattan distance (the sum of the horizontal distance along streets and the vertical distance along avenues) then one can de ne a city as being...
Data Structures for Maintaining Set Partitions (2003)
Michael A. Bender, Saurabh Sethia, Steven S. Skiena
Eciently maintaining the partition induced by a set of features is an important problem in building decision-tree classi ers. In order to identify a small set of discriminating features, we need the...
The Robustness of the Sum-of-Squares Algorithm for Bin Packing (2003)
Michael Bender Bryan, Michael A. Bender, Bryan Bradley, Geetha Jagannathan, Krishnan Pillaipakkamnatt
introduced the sum-ofsquares algorithm (SS) for online bin packing of integralsized items into integral-sized bins. They showed that for discrete distributions, the expected waste of SS is sublinear...
The Cost of Cache-Oblivious Searching (2003)
Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, ...
Tight bounds on the cost of cache-oblivious searching are proved. It is shown that no cache-oblivious search structure can guarantee that a search performs fewer than lg e log B N block transfers...
Algorithmic Support for Commodity-Based Parallel Computing Systems (2003)
Vitus J. Leung, Cynthia A. Phillips, Michael A. Bender, David P. Bunde
Follows Abstract The Computational Plant or Cplant is a commodity-based distributedmemory supercomputer under development at Sandia National Laboratories.
Online Dispersion Algorithms for Swarms of Robots (2003)
Tien-ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sandor Fekete
INTRODUCTION We illustrate algorithms for dispersing a swarm of primitive robots in a two-dimensional unknown environment R. Each robot in the swarm is equipped with a simple sensor that is able to...
Gerth Stølting Brodal, Michael A. Bender, Dongdong Ge, Simai He, John Iacono (polytechnic, ...
– Cache oblivious model
Approximation Algorithms for Average Stretch Scheduling (2003)
Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman
We study the basic problem of preemptive scheduling of a stream of jobs on a single processor.
Efficient Tree Layout in a Multilevel Memory Hierarchy (2002)
Alstrup, Stephen, Bender, Michael A., Demaine, Erik D., Farach-Colton, Martin, Rauhe, Theis, Thorup, Mikkel
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 during a search along a...
The Lazy Bureaucrat Scheduling Problem (2002)
Arkin, Esther M., Bender, Michael A., Mitchell, Joseph S. B., Skiena, Steven S.
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single ``machine'') who performs the tasks. A typical worker's objective is to minimize the...
Cache-oblivious priority queue and graph algorithm applications (2002)
Lars Arge, Bryan Holland-minkley, Michael A. Bender, J. Ian Munro, Erik D. Demaine
In this paper we develop an optimal cache-oblivious priority queue data structure, supporting insertion, deletion, and deletemin operations in O ( 1 B logM/B N) amortized memory B transfers, where M...
Scanning and traversing: maintaining data for traversals in a memory hierarchy (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine
Abstract. We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved on a RAM and on a...
Scanning and traversing: maintaining data for traversals in a memory hierarchy (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-coltony
Abstract. We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved on a RAM and on a...
Exponential structures for efficient cache-oblivious algorithms (2002)
Michael A. Bender, Richard Cole, Rajeev Raman
Abstract. We present cache-oblivious data structures based upon exponential structures. These data structures perform well on a hierarchical memory but do not depend on any parameters of the...
Analysis of heuristics for the Freeze-Tag Problem (2002)
Marcelo O. Sztainberg, Esther M. Arkin, Michael A. Bender
In the Freeze Tag Problem (FTP) we are given a swarm of n asleep (frozen or inactive) robots and a single awake (active) robot, and we want to awaken all robots in the shortest possible time. A robot...
The freeze-tag problem: How to wake up a swarm of robots (2002)
Esther M. Arkin, Michael A. Bender, Sandor P. Fekete, Martin Skutella
An optimization problem that naturally arises in the study of "swarm robotics " is to wake up a set of "asleep " robots, starting with only one "awake...
Two simplified algorithms for maintaining order in a list (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito
In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are...
Two simplified algorithms for maintaining order in a list (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-Colton, Jack Zito
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (2002)
Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Martin Skutella
An optimization problem that naturally arises in the study of "swarm robotics" is to wake up a set of "asleep" robots, starting with only one "awake" robot. One robot...
Online Scheduling of Parallel Programs on Heterogeneous Systems with Applications to Cilk (2002)
Michael A. Bender, Michael O. Rabin
We study the problem of executing parallel programs, in particular Cilk programs, on a collection of processors of di erent speeds. We consider a model in which each processor maintains an estimate...
The Lazy Bureaucrat Scheduling Problem (2002)
Esther M. Arkin, Michael A. Bender, Steven S. Skiena
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single \machine") who performs the tasks. A typical worker's objective is to minimize...
Efficient Tree Layout in a Multilevel Memory Hierarchy (2002)
Stephen Alstrup, Michael A. Bender, Erik D. Demaine, Martin Farach-colton, J. Ian Munro, Theis Rauhe, ...
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 during a search along a...
Testing Properties of Directed Graphs: Acyclicity and Connectivity (2002)
This paper initiates the study of testing properties of directed graphs. In particular, the paper considers the most basic property of directed graphs { acyclicity. Because the choice of...
A Locality-Preserving Cache-Oblivious Dynamic Dictionary (2002)
Michael A. Bender, Ziyang Duan, John Iacono, Jing Wu
This paper presents a simple dictionary structure designed for a hierarchical memory. The proposed data structure is cache oblivious and locality preserving. A cache-oblivious data structure has...
Vitus J. Leung, Cynthia A. Phillips, Jeanette R. Johnston, Esther M. Arkin, Michael A. Bender, ...
The Computational Plant or Cplant is a commodity-based supercomputer under development at Sandia National Laboratories. This paper describes resource-allocation strategies to achieve processor...
Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-colton
We study the problem of maintaining a dynamic ordered set subject to insertions, deletions, and traversals of k consecutive elements. This problem is trivially solved...
Analysis of Heuristics for the Freeze-Tag Problem (2002)
Marcelo O. Sztainberg, Esther M. Arkin, Michael A. Bender
In the Freeze Tag Problem (FTP) we are given a swarm of n asleep (frozen or inactive) robots and a single awake (active) robot, and we want to awaken all robots in the shortest possible time. A robot...
A Locality-Preserving Cache-Oblivious Dynamic Dictionary (2002)
Michael A. Bender, Suny Stony Brook, Ziyang Duan, John Iacono, Jing Wu
This paper presents a simple dictionary structure designed for a hierarchical memory. The proposed data structure is cache oblivious and locality preserving. A cache-oblivious data structure has...
Improved Algorithms for Stretch Scheduling (2002)
Michael A. Bender, S. Muthukrishnan, Rajmohan Rajaraman
We study the basic problem of preemptive scheduling of an online stream of jobs on a single processor. The ith job arrives at time r(i) and has processing time p(i) that is known at the time of its...
Online scheduling of parallel programs on heterogeneous systems with applications to Cilk (2002)
Michael A. Bender, Michael O. Rabin
1 Introduction One of the basic problems in parallel computing is how to execute a parallel program on a collection of heterogeneous processors, that is, processors of different and possibly changing...
Data Structures for Maintaining Set Partitions (2002)
Michael A. Bender, Saurabh Sethia, Steven S. Skiena
Eciently maintaining the partition induced by a set of features is an important problem in building decision-tree classi ers. In order to identify a small set of discriminating features, we need the...
Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments (2002)
Tien-ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sandor P. Fekete
We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire...
Efficient Tree Layout in a Multilevel Memory Hierarchy (2002)
Michael A. Bender, Erik D. Demaine, Martin Farach-Colton
We consider the problem of laying out a tree or trie in a hierarchical memory, where the tree/trie has a fixed parent/child structure. The goal is to minimize...
Efficient tree layout in a multilevel memory hierarchy (2002)
Michael A. Bender, Erik D. Demaine, Martin Farach-colton
Abstract. We consider the problem of laying out a tree or trie in a hierarchical memory, where the tree/trie has a fixed parent/child structure. The goal is to minimize the expected number of block...
Two simplified algorithms for maintaining order in a list (2002)
Michael A. Bender, Richard Cole, Erik D. Demaine, Martin Farach-colton, Jack Zito
Abstract. In the Order-Maintenance Problem, the objective is to maintain a total order subject to insertions, deletions, and precedence queries. Known optimal solutions, due to Dietz and Sleator, are...
When can you fold a map (2001)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Martin L. Demaine, Saurabh Sethia, ...
Abstract. We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple...
Finding least common ancestors in directed acyclic graphs (2001)
Michael A. Bender, Giridhar Pemmasani, Steven Skiena, Pavel Sumazin
One of the fundamental algorithmic problems on trees is how to nd the least common ancestor (LCA)
Succinct Strip Encoding of Triangle Meshes (2001)
Michael A. Bender, Outside Member, Esther M. Arkin, Xinyu Xiang, Xinyu Xiang, ...
OF THE DISSERTATION 2001 A fundamental algorithmic problem in computer graphics is that of computing a succinct encoding of a triangulation of a polygonal surface model in order to be able to...
Optimal covering tours with turn costs (2001)
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, S Ándor, P. Fekete, ...
Abstract. 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 sweeps out...
Succinct Strip Encoding of Triangle Meshes BY (2001)
Xinyu Xiang, Xinyu Xiang, Michael A. Bender, Outside Member, Esther M. Arkin, ...
We, the dissertation committe for the above candidate for the Doctor of Philosophy degree, hereby recommend acceptance of this dissertation.
When Can You Fold a Map? (2000)
Arkin, Esther M., Bender, Michael A., Demaine, Erik D., Demaine, Martin L., Mitchell, Joseph S. B., Sethia, Saurabh, ...
We explore the following problem: given a collection of creases on a piece of paper, each assigned a folding direction of mountain or valley, is there a flat folding by a sequence of simple folds?...
Cache-oblivious B-trees (2000)
Michael A. Bender, Erik D. Demaine, Martin Farach-colton
Abstract. This paper presents two dynamic search trees attaining near-optimal performance on any hierarchical memory. The data structures are independent of the parameters of the memory hierarchy,...
The LCA problem revisited (2000)
Michael A. Bender, Martín Farach-colton
Abstract. We present a very simple algorithm for the Least Common Ancestors problem. We thus dispel the frequently held notion that optimal LCA computation is unwieldy and unimplementable....
Performance guarantees for the TSP with a parameterized triangle inequality (2000)
Michael A. Bender, Chandra Chekuri
We consider the approximability of the tsp problem in graphs that satisfy a relaxed form of triangle inequality. More precisely, we assume that for some parameter 1, the distances satisfy the...
Scheduling Cilk multithreaded parallel programs on processors of different speeds (2000)
Michael A. Bender, Michael O. Rabin
We study the problem of executing parallel programs, in particular Cilk programs, on a collection of processors of different speeds. We consider a model in which each processor maintains an estimate...
Testing acyclicity of directed graphs in sublinear time (2000)
This paper initiates the study of testing properties of directed graphs. In particular, the paper considers the most basic property of directed graphs-- acyclicity. Because the choice of...
The LCA Problem Revisited (2000)
Michael Bender Suny, Michael A. Bender, Martn Farach-colton
We present a very simple algorithm for the Least Common Ancestor problem. We thus dispel the frequently held notion that an optimal LCA computation is unwieldy and unimplementable. Interestingly,...
Testing Acyclicity of Directed Graphs in Sublinear Time (2000)
This paper initiates the study of testing properties of directed graphs. In particular, the paper considers the most basic property of directed graphs -- acyclicity. Because the choice of...
Performance Guarantees for the TSP with a Parameterized Triangle Inequality (2000)
Michael A. Bender, Chandra Chekuri
We consider the approximability of the tsp problem in graphs that satisfy a relaxed form of triangle inequality. More precisely, we assume that for some parameter 1, the distances satisfy the...
Performance Guarantees for the TSP with a Parameterized Triangle Inequality (2000)
Michael Bender And, Michael A. Bender, Chandra Chekuri
. We consider the approximability of the tsp problem in graphs that satisfy a relaxed form of triangle inequality. More precisely, we assume that for some parameter 1, the distances satisfy the...
Scheduling Cilk multithreaded parallel programs on processors of different speeds (2000)
1. INTRODUCTION In this paper we study the problem of executing parallel programs, in particular Cilk programs, on processors that run at different and possibly changing speeds. We develop scheduling...
Cache-Oblivious B-Trees (2000)
Michael A. Bender, Erik D. Demaine, Martin Farach-colton
This paper presents two dynamic search trees attaining near-optimal performance on any hierarchical memory. The data structures are independent of the parameters of the memory hierarchy, e.g., the...
Cache-oblivious B-trees (2000)
Michael A. Bender, Erik D. Demaine, Martin Farach-colton
Abstract. This paper presents two dynamic search trees attaining near-optimal performance on any hierarchical memory. The data structures are independent of the parameters of the memory hierarchy,...
Data Structures for Maintaining Set Partitions (Extended Abstract) (2000)
Michael A. Bender, Saurabh Sethia, Steven Skiena
Michael A. Bender, Saurabh Sethia, and Steven Skiena Department of Computer Science, State University of New York at Stony Brook, Stony Brook, NY 11794-4400 USA, {bender|saurabh|skiena}@cs.sunysb.edu...
Cache-Oblivious B-Trees (2000)
Michael A. Bender, Erik D. Demaine, Martin Farach-colton
We present dynamic search-tree data structures that perform well in the setting of a hierarchical memory (including various levels of cache, disk, etc.), but do not depend on the number of memory...
The Lazy Bureaucrat Scheduling Problem (1999)
Esther M. Arkin, Michael A. Bender, Steven S. Skiena
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single \machine") who performs the tasks. The worker's objective may be to minimize the...
Performance Guarantees for the TSP with a Parameterized Triangle Inequality (1999)
Michael A. Bender, Chandra Chekuri
We consider the approximability of the tsp problem in graphs that satisfy a relaxed form of triangle inequality. More precisely, we assume that for some parameter ø 1, the distances satisfy the...
Efficient Data Structures for Maintaining Set Partitions (Extended Abstract) (1999)
Michael A. Bender, Saurabh Sethia, Steven S. Skiena
) Michael Bender Saurabh Sethia Steven Skiena Department of Computer Science State University of New York Stony Brook, NY 11794-4400 fbender---saurabh---skienag@cs.sunysb.edu April 22, 1999 1...
The Lazy Bureaucrat Scheduling Problem (1999)
Esther M. Arkin, Michael A. Bender, Steven S. Skiena
We introduce a new class of scheduling problems in which the optimization is performed by the worker (single "machine") who performs the tasks. The worker's objective may be to...
Abrahamson, Seymour, Bender, Michael A., Boecker, Bruce B., Gilbert, Ethel S., Scott, Bobby R.
Several studies designed to identify and quantify the potential health effects of accidental releases of radionuclides from nuclear power plants have been Sponsored by the Nuclear Regulatory...
New algorithms and metrics for scheduling / (1998)
Thesis (PhD)--Harvard University, 1998.
The Power of a Pebble: Exploring and Mapping Directed Graphs (1998)
Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil Vadhan
Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many works have focused on finding efficient solutions to restricted versions of the...
The Power of a Pebble: Exploring and Mapping Directed Graphs (1998)
Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil Vadhan
. Exploring and mapping an unknown environment is a fundamental problem, which is studied in a variety of contexts. Many works have focused on finding efficient solutions to restricted versions of...
The Power of a Pebble: Exploring and Mapping Directed Graphs (1998)
Michael A. Bender, Antonio Fernández, Juan Carlos, Dana Ron, Amit Sahai, Salil Vadhan
Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many works have focused on finding efficient solutions to restricted versions of the...
Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil Vadhan
Exploring and mapping an unknown environment is a fundamental problem that is studied in a variety of contexts. Many results have focused on finding efficient solutions to restricted versions of the...
Efficient asynchronous consensus with the value-oblivious adversary scheduler (1996)
Yonatan Aumann, Michael A. Bender
We address the problem of asynchronous consensus. In view of the
New algorithms for the disk scheduling problem (1996)
Matthew Andrews, Michael A. Bender, Lisa Zhang
Processor speed and memory capacity are increasing several times faster than disk speed. This disparity suggests that disk I/O performance will become an important bottleneck. Methods are needed for...
Fault Tolerant Data Structures (1996)
Yonatan Aumann, Michael A. Bender
We consider the tolerance of data structures to memory faults. We observe that many pointer-based data structures (e.g. linked lists, trees, etc.) are highly nonresilient to faults. A single fault in...
Efficient Execution of Nondeterministic Parallel Programs on Asynchronous Systems (1996)
Yonatan Aumann, Michael A. Bender, Lisa Zhang
We consider the problem of asynchronous execution of parallel programs. The original program is assumed to be designed for a synchronous system, while the actual system may be asynchronous. We seek...
New Algorithms for the Disk Scheduling Problem (1996)
Michael A. Bender, Matthew Andrews, Lisa Zhang
celeration phase. In particular, this radial movement is determined by a reachability function f(`). In a rotation of angle `, the function f(`) represents the maximum radial distance the head can...
Efficient Asynchronous Consensus with the Value-Oblivious Adversary Scheduler (1996)
Yonatan Aumann, Michael A. Bender
We consider the power given to adversary scheduler of an asynchronous system and define the value-oblivious scheduler. At each step this scheduler determines the next processor to operate based on...
The power of team exploration: Two robots can learn unlabeled directed graphs (1994)
We show that two cooperating robots can learn ex-actly any strongly-connected directed graph with n in-distinguishable nodes in expected tame polynomial in n. We introduce a new type of homing...
The power of team exploration: Two robots can learn unlabeled directed graphs (1994)
Michael A. Bender, Donna K. Slonim
We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. Weintroduce a new type of homing sequence...
The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs (1994)
Michael A. Bender, Donna K. Slonim
We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. We introduce a new type of homing sequence...
The Power of Team Exploration: Two Robots Can Learn Unlabeled Directed Graphs (1994)
Michael A. Bender, Donna K. Slonim
We show that two cooperating robots can learn exactly any strongly-connected directed graph with n indistinguishable nodes in expected time polynomial in n. We introduce a new type of homing sequence...
Michael A. Bender, Sándor P. Fekete, Er Kröller, Valentin Polishchuk
Abstract. We introduce and study the minimum-backlog problem (MBP). The MBP arises in sensor networks and is related to the classic k-server problem. It can be understood as a 2-person game played on...
Michael A. Bender, S Ándor, P. Fekete, Alexander Kr Öller, Valentin Polishchuk, ...
Abstract. We introduce and study the minimum-backlog problem (MBP). The MBP arises in sensor networks and is related to the classic k-server problem. It can be understood as a 2-person game played on...
Vita.
The Uniformity of Normalized Radiation-Induced Mutation Rates among Different Species
Wolff, Sheldon, Abrahamson, Seymour, Bender, Michael A., Conger, Alan D.
The Uniformity of Normalized Radiation-Induced Mutation Rates among Different Species
Wolff, Sheldon, Abrahamson, Seymour, Bender, Michael A., Conger, Alan D.
Improved Approximation Algorithms for the Freeze-Tag Problem
Esther M. Arkin, Michael A. Bender, Dongdong Ge, Simai He
In the Freeze-Tag Problem, the objective is to awaken a set of \asleep" robots, starting with only one \awake" robot. A robot awakens a sleeping robot by moving to the sleeping robot's...