Christian Scheideler, Andrea W. Richa
Dealing with interference is one of the primary challenges to solve in the design of protocols for wireless ad-hoc networks. Most of the work in the literature assumes localized or hopbased...
Evaluation of Physical Carrier Sense Based Backbone Maintenance in Mobile Ad Hoc Networks (2009)
Sapna Deval, Luke Ritchie, Martin Reisslein, Andrea W. Richa
Physical carrier sensing has to date mainly been exploited for improving medium access control in wireless networks. Recently, a parallel algorithm striving to extensively exploit physical carrier...
Evaluation of Physical Carrier Sense Based Backbone Maintenance in Mobile Ad Hoc Networks (2009)
Sapna Deval, Luke Ritchie, Martin Reisslein, Andrea W. Richa
Physical carrier sensing has to date mainly been exploited for improving medium access control in wireless networks. Recently, a parallel algorithm striving to extensively exploit physical carrier...
Michael Mitzenmacher, Andrea W. Richa, Ramesh Sitaraman Z
To motivate this survey, we begin with a simple problem that demonstrates a
Goran Konjevod, Andrea W. Richa
Abstract. In this paper, we formalize the problem of nding a routing path for the streaming of continuous media (e.g., video or audio les) that maximizes the probability that the streaming is...
Rajmohan Rajaraman, Andrea W. Richa
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...
The power of two random choices: a survey of techniques and results (2001)
Michael Mitzenmacher, Andrea W. Richa, Ramesh Sitaraman
To motivate this survey, we begin with a simple problem that demonstrates a powerful fundamental idea. Suppose that n balls are thrown into n bins, with
Hai Huang, Andrea W. Richa, Michael Segal
The main contributions of this paper are two-fold. First, we present a simple, general framework for obtaining ecient constant-factor approximation algorithms for the mobile piercing set (MPS)...
Richard Cole Bruce, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andrea W. Richa, Klaus Schroder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
New Approximation Techniques for Some Ordering Problems, (1997)
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...
Fast Algorithms for Finding O(Congestion + Dilation) Packet Routing Schedules, (1997)
Leighton, F. T., Maggs, Bruce M., Richa, Andrea W.
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...
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...
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...