Daniel Dominic Sleator

SODA Conference 2006 Conference Paper

O (log log n )-competitive dynamic binary search trees

• Chengwen Chris Wang
• Jonathan Derryberry
• Daniel Dominic Sleator

SODA Conference 1991 Conference Paper

Fully Persistent Lists with Catenation

• James R. Driscoll
• Daniel Dominic Sleator
• Robert Endre Tarjan

SODA Conference 1991 Conference Paper

Randomized Competitive Algorithms for the List Update Problem

• Sandy Irani
• Nick Reingold
• Jeffery R. Westbrook
• Daniel Dominic Sleator

STOC Conference 1988 Conference Paper

Competitive Algorithms for On-line Problems

• Mark S. Manasse
• Lyle A. McGeoch
• Daniel Dominic Sleator

An on-line problem is one in which an algorithm must handle a sequence of requests, satisfying each request without knowledge of the future requests. Examples of on-line problems include scheduling the motion of elevators, finding routes in networks, allocating cache memory, and maintaining dynamic data structures. A competitive algorithm for an on-line problem has the property that its performance on any sequence of requests is within a constant factor of the performance of any other algorithm on the same sequence. This paper presents several general results concerning competitive algorithms, as well as results on specific on-line problems.

STOC Conference 1987 Conference Paper

Two Algorithms for Maintaining Order in a List

• Paul F. Dietz
• Daniel Dominic Sleator

The order maintenance problem is that of maintaining a list under a sequence of Insert and Delete operations, while answering Order queries (determine which of two elements comes first in the list). We give two new algorithms for this problem. The first algorithm matches the O (1) amortized time per operation of the best previously known algorithm, and is much simpler. The second algorithm permits all operations to be performed in O (1) worst-case time.

FOCS Conference 1986 Conference Paper

Competitive Snoopy Caching

• Anna R. Karlin
• Mark S. Manasse
• Larry Rudolph
• Daniel Dominic Sleator

In a snoopy cache multiprocessor system, each processor has a cache in which it stores blocks of data. Each cache is connected to a bus used to communicate with the other caches and with main memory. For several of the proposed models of snoopy caching, we present new on-line algorithms which decide, for each cache, which blocks to retain and which to drop in order to minimize communication over the bus. We prove that, for any sequence of operations, our algorithms' communication costs are within a constant factor of the minimum required for that sequence; for some of our algorithms we prove that no on-line algorithm has this property with a smaller constant.

STOC Conference 1986 Conference Paper

Making Data Structures Persistent

• James R. Driscoll
• Neil Sarnak
• Daniel Dominic Sleator
• Robert Endre Tarjan

STOC Conference 1986 Conference Paper

Rotation Distance, Triangulations, and Hyperbolic Geometry

• Daniel Dominic Sleator
• Robert Endre Tarjan
• William P. Thurston

STOC Conference 1984 Conference Paper

Amortized Efficiency of List Update Rules

• Daniel Dominic Sleator
• Robert Endre Tarjan

STOC Conference 1983 Conference Paper

Self-Adjusting Binary Trees

• Daniel Dominic Sleator
• Robert Endre Tarjan

STOC Conference 1981 Conference Paper

A Data Structure for Dynamic Trees

• Daniel Dominic Sleator
• Robert Endre Tarjan

We propose a data structure to maintain a collection of vertex-disjoint trees under a sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by deleting an edge. Our data structure requires O(log n) time per operation when the time is amortized over a sequence of operations. Using our data structure, we obtain new fast algorithms for the following problems: (1) Computing deepest common ancestors. (2) Solving various network flow problems including finding maximum flows, blocking flows, and acyclic flows. (3) Computing certain kinds of constrained minimum spanning trees. (4) Implementing the network simplex algorithm for the transshipment problem. Our most significant application is (2); we obtain an O(mn log n)-time algorithm to find a maximum flow in a network of n vertices and m edges, beating by a factor of log n the fastest algorithm previously known for sparse graphs.

FOCS Conference 1980 Conference Paper

Biased 2-3 Trees

• Samuel W. Bent
• Daniel Dominic Sleator
• Robert Endre Tarjan

We describe a new data structure for maintaining collections of weighted items. The access time for an item of weight w in a collection of total weight W is proportional to log(W/w) in the worst case (which is optimal in a certain sense), and several other useful operations can be made to work just, as fast. The data structure is simpler than previous proposals, but the running time must be amortized over a sequence of operations to achieve the time bounds.