Mark S. Manasse

SODA Conference 1993 Conference Paper

On-line Choice of On-line Algorithms

• Yossi Azar
• Andrei Z. Broder
• Mark S. Manasse

SODA Conference 1990 Conference Paper

Competitive Randomized Algorithms for Non-Uniform Problems

• Anna R. Karlin
• Mark S. Manasse
• Lyle A. McGeoch
• Susan S. Owicki

STOC Conference 1990 Conference Paper

The Number Field Sieve

• Arjen K. Lenstra
• Hendrik W. Lenstra Jr.
• Mark S. Manasse
• John M. Pollard

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.

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.