Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Andr'ea W. Richa, Ramesh K. Sitaraman, Eli Upfal
We consider the problem of extending the analysis of balls and bins processes to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and deletions...
C. Greg Plaxton, Rajmohan Rajaraman, Andr'ea W. Richa
Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time. To ensure both fast access to the objects as well as efficient utilization...
Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
A Data Tracking Scheme for General Networks (2001)
Rajmohan Rajaraman Andr'ea, Rajmohan Rajaraman, Andr'ea W. Richa, Berthold Vocking
Consider an arbitrary distributed network in which large numbers of objects are continuously being created, replicated, and destroyed. A basic problem arising in such an environment is that of...
New approximation techniques for some ordering problems (1998)
We describe logarithmic times optimal approximation algorithms for the NP-hard graph optimization problems of minimum linear arrangement, minimum containing interval graph, and minimum storage--time...
On Balls and Bins with Deletions (1998)
Richard Cole Alan, Bruce M. Maggs, Michael Mitzenmacher, Andr'ea W. Richa, Ramesh K. Sitaraman, Eli Upfal
We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested...
New Approximation Techniques for Some Ordering Problems (1998)
Satish Rao, Andréa W. Richa, Andr'ea W. Richa
We describe O(log n) times optimal approximation algorithms for the NP-hard graph optimization problems of minimum linear arrangement, minimum containing interval graph, and minimum storage-time...
On Balls and Bins with Deletions (1998)
Richard Cole, Alan Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Andr'ea W. Richa, ...
We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested...
Accessing nearby copies of replicated objects in a distributed environment (1997)
C. Greg Plaxton, Rajmohan Rajaraman, Andr'ea W. Richa
Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time. To ensure both fast access to the objects as well as efficient utilization...
Accessing Nearby Copies of Replicated Objects in a Distributed Environment (1997)
C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa, Andr'ea W. Richa
Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time. To ensure both fast access to the objects as well as efficient utilization...
Accessing Nearby Copies of Replicated Objects in a Distributed Environment (1997)
C. Greg Plaxton, Rajmohan Rajaraman, Andrea W. Richa, Andr'ea W. Richa
Consider a set of shared objects in a distributed network, where several copies of each object may exist at any given time. To ensure both fast access to the objects as well as efficient utilization...
Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules (1996)
Tom Leighton, Bruce Maggs, A.W. Richa, Andr'ea W. Richa
In 1988, Leighton, Maggs, and Rao showed that for any network and any set of packets whose paths through the network are fixed and edge-simple, there exists a schedule for routing the packets to...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh Leighton, Bhaskar Ghosh, F. T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...
Tight Analyses of Two Local Load Balancing Algorithms (1995)
Bhaskar Ghosh, F.T. Leighton, Bruce M. Maggs, S. Muthukrishnan, C. Greg Plaxton, R. Rajaraman, ...
This paper presents an analysis of the following load balancing algorithm. At each step, each node in a network examines the number of tokens at each of its neighbors and sends a token to each...