Compact Routing with Slack in Low Doubling Dimension ABSTRACT (2009)
Goran Konjevod, Andréa W. Richa, Hai Yu, Donglin Xia
We consider the problem of compact routing with slack in networks of low doubling dimension. Namely, we seek nameindependent routing schemes with (1 + ǫ) stretch and polylogarithmic storage at each...
Compact Routing with Slack in Low Doubling Dimension ABSTRACT (2009)
Goran Konjevod, Andréa W. Richa, Hai Yu, Donglin Xia
We consider the problem of compact routing with slack in networks of low doubling dimension. Namely, we seek nameindependent routing schemes with (1 + ɛ) stretch and polylogarithmic storage at each...
Abstract Optimal Scale-free Compact Routing Schemes in Networks of Low Doubling Dimension ∗ (2008)
Goran Konjevod, Andréa W. Richa, Donglin Xia
We present optimal-stretch scale-free compact routing schemes for networks of low doubling dimension, in both the name-independent and name-dependent models. Our name-independent algorithm is the...
Richard Cole, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
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...
Compact Routing with Slack in Low Doubling Dimension ABSTRACT (2008)
Goran Konjevod, Andréa W. Richa, Hai Yu, Donglin Xia
We consider the problem of compact routing with slack in networks of low doubling dimension. Namely, we seek nameindependent routing schemes with (1 + ǫ) stretch and polylogarithmic storage at each...
Richard Cole, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
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...
Application-oriented Self-organizing Hierarchical Clustering in Dynamic Networks (2008)
Andréa W. Richa, Katia Obraczka, Arunabha Sen
We are currently developping a suite of self-organizing clustering algorithms which will automatically adapt to network dynamics in response to application-speci c requirements. As a starting point,...
Optimal scale-free compact routing schemes in doubling networks (2007)
Goran Konjevod, Andréa W. Richa, Donglin Xia
We consider compact routing schemes in networks of low doubling dimension, where the doubling dimension is the least value α such that any ball in the network can be covered by at most 2 α balls of...
Optimal scale-free compact routing schemes in doubling networks (2007)
Goran Konjevod, Goran Konjevod, Andréa W. Richa, Andréa W. Richa, Donglin Xia, Donglin Xia
Note: This paper combines two conference papers:
On sampling in higher-dimensional peer-to-peer systems (2006)
Goran Konjevod, Andréa W. Richa, Donglin Xia
We present fully distributed algorithms for random sampling of nodes in peer-to-peer systems, extending and generalizing the work of King and Saia [Proceedings of PODC 2004] from simple Chord-like...
Dynamic Coverage in Ad-Hoc Sensor Networks”, pp 9-17 (2005)
Hai Huang, Andréa W. Richa, Michael Segal
Ad-hoc networks of sensor nodes are in general semi-permanently deployed. However, the topology of such networks continuously changes over time, due to the power of some sensors wearing out, to new...
Hai Huang, Andréa 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)...
Fast algorithms for finding O(congestion + dilation) packet routing schedules (1999)
Tom Leighton, Bruce Maggs, Andréa 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 (1999)
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...
On Balls and Bins with Deletions (1998)
Richard Cole, Alan Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Ramesh Sitaraman, ...
Microsystems. The views and conclusions contained here are those of the authors and should not be interpreted as necessarily representing the official policies or
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
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 (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...
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Friedhelm Meyer, Heide Michael Mitzenmacher, ...
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 (1998)
We describe logarithmic approximation algorithms for the NP-hard graph optimization problems of minimum linear arrangement, minimum containing interval graph, and minimum storage{time product. This...
Fast Algorithms for Finding O(Congestion+Dilation) Packet Routing Schedules (1996)
F. T. Leighton, Bruce M. Maggs, Andréa 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, 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...
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...