Adaptive Algorithms for (2007)
Systems Jeffery, Jeffery Westbrook, Lenore Zuck
: We describe a fault-tolerant distributed storage system for local area networks. Our system implements Persistent, Associative, Shared Object (PASO) memory. A PASO memory stores a set of data...
Cellular Embeddings and Network Flow (2007)
This paper presents an algorithm for network flow that uses the graph decomposition introduced by Frederickson, called a hammock decomposition, to achieve improved running times on sparse graphs. The...
Generating Adversaries for Request-Answer Games (2000)
Todd Gormley, Nicholas Reingold, Eric Torng, Jeffery Westbrook
Introduction and Results The k-server conjecture postulates the existence of an algorithm which is k-competitive for all values of k on all metric spaces. We give a procedure which is guaranteed to...
Robot Navigation with Distance Queries (2000)
Dana Angluin, Jeffery Westbrook, Wenhong Zhu
We consider the problem of online robot navigation in an unfamiliar two-dimensional environment, using comparatively limited sensing information. In particular, the robot has local sensors to detect...
On-line Algorithms: Competitive Analysis and Beyond (1999)
Steven Phillips, Jeffery Westbrook
this article, but rather a deep principle of on-line analysis known as Yao's minimax theorem [Yao, 1980]. This theorem is actually an adaptation of the famous minimax theorem of game theory [von...
Competitive On-Line Algorithms for Distributed Data Management (1999)
Carsten Lund, Nick Reingold, Jeffery Westbrook, Dicky Yan
. Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and updated by...
Competitive On-Line Algorithms For Distributed Data Management (1999)
Carsten Lund, Nick Reingold, Jeffery Westbrook, Dicky Yan
.<F3.887e+05> Competitive on-line algorithms for data management in a network of processors are studied in this paper. A data object such as a file or a page of virtual memory is to be read and...
Maintenance of a Minimum Spanning Forest in a Dynamic Planar Graph, (1998)
Eppstein, David, Italiano, Giuseppe F., Tamassia, Roberto, Tarjan, Robert E., Westbrook, Jeffery
We give efficient algorithms for maintaining a minimum spanning forest of a planar graph subject to on-line modifications. The modifications supported include changes in the edge weights, and...
Maintaining the classes of 4-edge-connectivity in a graph on-line (1998)
Yefim Dinitz, Jeffery Westbrook
Two vertices of an undirected graph are called k-edge-connected if there exist k edge-disjoint paths between them (equivalently: they cannot be disconnected by the removal of less than k edges from...
A survey of self-organizing data structures (1998)
Susanne Albers, Jeffery Westbrook
Abstract. We survey results on self-organizing data structures for the search problem and concentrate on two very popular structures: the unsorted linear list, and the binary search tree. For the...
A Survey of Self-Organizing Data Structures (1998)
Susanne Albers, Jeffery Westbrook
This paper surveys results in the design and analysis of self-organizing data structures for the search problem. The general search problem in pointer data structures can be phrased as follows. The...
Dynamic 2-Connectivity With Backtracking (1998)
Johannes La Poutre, Jeffery Westbrook
.<F3.83e+05> We give algorithms and data structures that maintain the 2-edge and 2-vertexconnected components of a graph under insertions and deletions of edges and vertices, where deletions...
Off-line Algorithms for The List Update Problem (1996)
Nick Reingold, Jeffery Westbrook
Optimum off-line algorithms for the list update problem are investigated. The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum...
Off-line Algorithms for The List Update Problem (1995)
Nick Reingold, Jeffery Westbrook
Optimum off-line algorithms for the list update problem are investigated. The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum...
Load Balancing for Response Time (1995)
A centralized scheduler must assign tasks to servers, processing on-line a sequence of task arrivals and departures. Each task runs for an unknown length of time, but comes with a weight that...
Approximation Algorithms for the Class Steiner Tree Problem (1994)
The class Steiner tree problem (CSP) [18, 19, 29] is a generalization of the well known Steiner tree problem (STP) [17, 35]; one is given a weighted undirected graph in which the nodes are...
Page Migration Algorithms Using Work Functions (1994)
Marek Chrobak, Lawrence L. Larmore, Nick Reingold, Jeffery Westbrook
The page migration problem occurs in managing a globally addressed shared memory in a multiprocessor system. Each physical page of memory is located at a given processor, and memory references to...
Adaptive Algorithms for PASO Systems (1994)
Jeffery Westbrook, Lenore Zuck
: We describe a fault-tolerant distributed storage system for local area networks. Our system implements Persistent, Associative, Shared Object (PASO) memory. A PASO memory stores a set of data...
Load Balancing for Response Time (1994)
A centralized scheduler must assign tasks to servers, processing on-line a sequence of task arrivals and departures. Each task runs for an unknown length of time, but comes with a weight that...
Online Load Balancing and Network Flow (1993)
Steven Phillips, Jeffery Westbrook
In this paper we study two problems that can be viewed as on-line games on a dynamic bipartite graph. The first problem is on-line load balancing with preemption. A centralized scheduler must assign...
Short Encodings of Planar Graphs and Maps (1993)
Kenneth Keeler, Jeffery Westbrook
We discuss space-efficient encoding schemes for planar graphs and maps. Our results improve on the constants of previous schemes and can be achieved with simple encoding algorithms. They are...
A Linear Algorithm for Analysis of Minimum Spanning and Shortest Path Trees of Planar Graphs (1992)
Heather Booth, Jeffery Westbrook
We give a linear time and space algorithm for analyzing trees in planar graphs. The algorithm can be used to analyze the sensitivity of a minimum spanning tree to changes in edge costs, to find its...
Randomized Competitive Algorithms for the List Update Problem (1992)
Nick Reingold, Jeffery Westbrook, Daniel D. Sleator
We prove upper and lower bounds on the competitiveness of randomized algorithms for the list update problem of Sleator and Tarjan. We give a simple and elegant randomized algorithm that is more...
Fast Incremental Planarity Testing (1992)
The incremental planarity testing problem is to perform the following operations on a biconnected planar graph G of at most n vertices: test if an edge can be added between two vertices while...
Maintenance of a Minimum Spanning Forest in a Dynamic Plane Graph (1992)
David Eppstein, Giuseppe F. Italiano, Roberto Tamassia, Robert E. Tarjan, Jeffery Westbrook, Moti Yung
We give an efficient algorithm for maintaining a minimum spanning forest of a plane graph subject to on-line modifications. The modifications supported include changes in the edge weights, and...
Randomized Algorithms For Multiprocessor Page Migration
. The page migration problem is to manage a globally addressed shared memory in a multiprocessor system. Each physical page of memory is located at a given processor, and memory references to that...
Adaptive Parallelism with Piranha
Nicholas Carriero, David Gelernter, David Kaminsky, Jeffery Westbrook
"Adaptive parallelism" refers to parallel computations on a dynamically changing set of processors: processors may join or withdraw from the computation as it proceeds. Networks of fast...