Mortal Multi-Armed Bandits (2009)
Deepayan Chakrabarti, Filip Radlinski, Ravi Kumar, Eli Upfal
We formulate and study a new variant of the k-armed bandit problem, motivated by e-commerce applications. In our model, arms have (stochastic) lifetime after which they expire. In this setting an...
Adapting to a Changing Environment: the Brownian Restless Bandits (2009)
In the multi-armed bandit (MAB) problem there are k distributions associated with the rewards of playing each of k strategies (slot machine arms). The reward distributions are initially unknown to...
COMPUTINGWITHNOISYINFORMATION* (2008)
Uriel Feiget, Prabhakar Raghavant, David Peleg, Eli Upfal
Abstract. This paper studies the depth of noisy decision trees in which each node gives the wrong answer with some constant probability. In the noisy Boolean decision tree model, tightbounds are...
Multi-Armed Bandits in Metric Spaces (2008)
Kleinberg, Robert, Slivkins, Aleksandrs, Upfal, Eli
In a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of trials so as to maximize the total payoff of the chosen strategies. While the performance of...
() 1994 Society for Industrial and Applied Mathematics (2008)
Andrei Z. Broder, Anna R. Karlint, Prabhakar Raghavan, Eli Upfal
undirected graphs can be solved in log space and O(mn) time [m is the number of edges and n is the number of vertices] by a probabilistic algorithm that simulates a random walk, or in linear time and...
Computing Near Optimal Strategies for Stochastic Investment Planning Problems (2008)
Milos Hauskrecfat, Gopal P, Eli Upfal
We present efficient techniques for computing near optimal strategies for a class of stochastic commodity trading problems modeled as Markov decision processes (MDPs). The process has a continuous...
Abstract How much can hardware Extended Abstract (2008)
Allan Borodin, Prabhakar Raghavant, Baruch Schieber, Eli Upfal
help routing?
Eli Upfal, Ibm Re. Seurch, Luborutory Sun Jose
Abstract. The power of shared-memory in models of parallel computation is studied, and a novel distributed data structure that eliminates the need for shared memory without significantly increasing...
IEEE J. ON SELECT. AREAS COMMUN. 1 Building Low-Diameter Peer-to-Peer Networks (2008)
Gopal P, Prabhakar Raghavan, Eli Upfal
Abstract—Peer-to-Peer (P2P) computing has emerged as a significant paradigm for providing distributed services, in particular search and data sharing. Current P2P networks (e.g., Gnutella) are...
Propagating Knapsack Constraints in Sublinear Time ∗ (2008)
Irit Katriel, Meinolf Sellmann, Eli Upfal, Pascal Van Hentenryck
We develop an efficient incremental version of an existing cost-based filtering algorithm for the knapsack constraint. On a universe of n elements, m invocations of the algorithm require a total of...
Efficient methods for computing investment strategies for multi-market commodity trading (2008)
Milos Hauskrecht, Luis Ortiz, Ioannis Tsochantaridis, Eli Upfal
The focus of this work is the computation of efficient strategies for commodity trading in a multi-market environment. In today’s “global economy ” commodities are often bought in one location...
Entropy-Based Bounds for Online Algorithms (2008)
We focus in this work on an aspect of online computation that is not addressed by the standard competitive analysis. Namely, identifying request sequences for which non-trivial online algorithms are...
Steady state analysis of balanced-allocation routing. Random Structures and Algorithms (2008)
Aris Anagnostopoulos, Ioannis Kontoyiannis, Eli Upfal
We compare the long-term, steady-state performance of a variant of the standard Dynamic Alternative Routing (DAR) technique commonly used in telephone and ATM networks, to the performance of a...
Design and Analysis of Dynamic Processes: A Stochastic Approach (2008)
Abstract. Past research in theoretical computer science has focused mainly on static computation problems, where the input is known before the start of the computation and the goal is to minimize the...
The hiring problem and Lake Wobegon strategies (2008)
Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii
We introduce the hiring problem, in which a growing company continuously interviews and decides whether to hire applicants. This problem is similar in spirit but quite different from the well-studied...
The hiring problem and Lake Wobegon strategies (2008)
Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal, Sergei Vassilvitskii
We introduce the hiring problem, in which a growing company continuously interviews and decides whether to hire applicants. This problem is similar in spirit but quite different from the well-studied...
The hiring problem and Lake Wobegon strategies (2008)
Andrei Z. Broder, Adam Kirsch, Ravi Kumar, Michael Mitzenmacher, Eli Upfal
We introduce the hiring problem, in which a growing company continuously interviews and decides whether to hire applicants. This problem is similar in spirit but quite different from the well-studied...
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...
ABSTRACT The Web as a graph (2007)
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew S. Tomkins, Eli Upfal
The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph has about a billion nodes today, several billion links, and appears to grow...
Static and Dynamic Evaluation of QoS Properties (2007)
Efficient utilization of modern high bandwidth communication networks relies on statistical multiplexing of many logical channels through one physical channel. Communication requests typically...
Computing Global Strategies for Multi-Market Commodity Trading (2007)
Milos Hauskrecht, Luis Ortiz, Ioannis Tsochantaridis, Eli Upfal
The focus of this work is the computation of ecient strategies for commodity trading in a multi-market environment. In today's "global economy" commodities are often bought in one...
A Wait-Free Sorting Algorithm (2007)
Nir Shavit, Eli Upfal, Asaph Zemach
Sorting is one of a set of fundamental problems in computer science. In this paper we present the first wait-free algorithm for sorting an input array of size N using P N processors to achieve...
ABSTRACT The Web as a graph (2007)
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, Eli Upfal
The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph has about a billion nodes today, several billion links, and appears to grow...
Prabhakar Raghavan, Sridhar Rajagopalan, D Sivakumar, Andrew Tomkins, Eli Upfal
The web may be viewed as a directed graph each of whose vertices is a static HTML web page, and each of whose edges corresponds to a hyperlink from one web page to another. In this paper we propose...
Gopal Pandurangan, Prabhakar Raghavan, Eli Upfal
Building P2P networks with good topological properties
Static and Dynamic Evaluation of QoS Properties (2007)
Ecient utilization of modern high bandwidth communication networks relies on statistical multiplexing of many logical channels through one physical channel. Communication requests typically include...
Static and Dynamic Evaluation of QoS Properties (2007)
Ecient utilization of modern high bandwidth communication networks relies on statistical multiplexing of many logical channels through one physical channel. Communication requests typically include...
Gopal Pandurangan, Prabhakar Raghavan, Eli Upfal
Recent work on modeling the Web graph has dwelt on capturing the degree distributions observed on the Web. Pointing out that this represents a heavy reliance on \local " properties of the...
Abstract. We study the extent to which complex hardware can speed up routing. Specifically, we consider the following questions. How much does adaptive routing improve over oblivious routing? How...
Andrei Z. Broder, Alan M. Frieze, Eli Upfal
We prove a sucient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of static...
Stochastic models for the web graph Ravi Kumar (2007)
Prabhakar Raghavan, Sridhar Rajagopalan, D Sivakumar, Andrew Tomkins, Eli Upfal
The web may be viewed as a directed graph each of whose vertices is a static HTML web page, and each of whose edges corresponds to a hyperlink from one web page to another. In this paper we propose...
Ecient methods for computing investment strategies for multi-market commodity trading (2007)
Milos Hauskrecht, Luis Ortiz, Ioannis Tsochantaridis, Eli Upfal
The focus of this work is the computation of ecient strategies for commodity trading in a multi-market environment. In today's \global economy " commodities are often bought in one...
Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems (2007)
Irit Katriel, Claire Kenyon-mathieu, Eli Upfal
We define and study two versions of the bipartite matching problem in the framework of two-stage stochastic optimization with recourse. In one version the uncertainty is in the second stage costs of...
07391 Abstracts Collection -- Probabilistic Methods in the Design and Analysis of Algorithms (2007)
Dietzfelbinger, Martin, Teng, Shang-Hua, Upfal, Eli, Vöcking, Berthold
From 23.09.2007 to 28.09.2007, the Dagstuhl Seminar 07391 "Probabilistic Methods in the Design and Analysis of Algorithms''was held in the International Conference and Research Center (IBFI), Schloss...
Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input (2005)
Aris Anagnostopoulos, Adam Kirsch, Eli Upfal
We study the long-term (steady state) performance of a simple, randomized, local load balancing technique under a broad range of input conditions. We assume a system of n processors connected by an...
Steady State Analysis of Balanced-Allocation Routing (2005)
Aris Anagnostopoulos Ioannis, Ioannis Kontoyiannis, Eli Upfal, A. Z. Broder, A. R. Karlin, E. Upfal, ...
We compare the long-term, steady-state performance of a variant of the standard Dynamic Alternative Routing (DAR) technique commonly used in telephone and ATM networks, to the performance of a...
Load Balancing in Arbitrary Network Topologies with Stochastic Adversarial Input (2005)
Aris Anagnostopoulos, Adam Kirsch, Eli Upfal
We study the long-term (steady state) performance of a simple, randomized, local load balancing technique under a broad range of input conditions. We assume a system of n processors connected by an...
Efficient Communication in an Ad-Hoc Network (2003)
Abraham Flaxman, Alan Frieze, Eli Upfal
We model the dynamic of an ad-hoc sensor network as a continuum percolation model, and prove that a simple, local ooding, technique yields an efficient communication protocol in that setting.
Stability and Efficiency of a Random Local Load Balancing Protocol (2003)
Aris Anagnostopoulos, Adam Kirsch, Eli Upfal
We study the long term (steady state) performance of a simple, randomized, local load balancing technique. We assume a system of n processors connected by an arbitrary network topology. Jobs are...
A Simple and Deterministic Competitive Algorithm for Online Facility Location (2003)
Aris Anagnostopoulos, Russell Bent, Eli Upfal, Pascal Van Hentenryck
This paper presents a deterministic and e#cient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also...
Gopal Pandurangan Member, Gopal P, Prabhakar Raghavan, Eli Upfal
Peer-to-Peer (P2P) computing has emerged as a significant paradigm for providing distributed services, in particular search and data sharing. Current P2P networks (e.g., Gnutella) are constructed by...
Stability and Efficiency of a Random Local Load Balancing Protocol (2003)
Aris Anagnostopoulos, Adam Kirsch, Eli Upfal
We study the long term (steady state) performance of a simple, randomized, local load balancing technique. We assume a system of Ò processors connected by an arbitrary network topology. Jobs are...
Stability and Efficiency of a Random Local Load Balancing Protocol (2003)
Aris Anagnostopoulos, Adam Kirsch, Eli Upfal
We study the long term (steady state) performance of a simple, randomized, local load balancing technique. We assume a system of n processors connected by an arbitrary network topology. Jobs are...
A Simple and Deterministic Competitive Algorithm for Online Facility Location (2003)
Aris Anagnostopoulos, Russell Bent, Eli Upfal, Pascal Van Hentenryck
This paper presents a deterministic and efficient algorithm for online facility location. The algorithm is based on a simple hierarchical partitioning and is extremely simple to implement. It also...
Steady State Analysis of Balanced-Allocation Routing (2003)
Aris Anagnostopoulos, Ioannis Kontoyiannis, Eli Upfal
We compare the long-term, steady-state performance of a variant of the standard Dynamic Alternative Routing (DAR) technique commonly used in telephone and ATM networks, to the performance of a...
Steady state analysis of balanced-allocation routing (2002)
Anagnostopoulos, Aris, Kontoyiannis, Ioannis, Upfal, Eli
We compare the long-term, steady-state performance of a variant of the standard Dynamic Alternative Routing (DAR) technique commonly used in telephone and ATM networks, to the performance of a...
Using PageRank to Characterize Web Structure (2002)
Gopal Pandurangan Prabhakar, Gopal P, Prabhakar Raghavan, Eli Upfal
Recent work on modeling the Web graph has dwelt on capturing the degree distributions observed on the Web. Pointing out that this represents a heavy reliance on "local" properties of the...
Building low-diameter p2p networks (2001)
Gopal Pandurangan, Prabhakar Raghavan, Eli Upfal
In a peer-to-peer (P2P) network, nodes connect into an existing network and participate in providing and availing of services. There is no dichotomy between a central server and distributed clients....
Can entropy characterize performance of online algorithms (2001)
We focus in this work on an aspect of online computation that is not addressed by the standard competitive analysis. Namely, identifying request sequences for which non-trivial online algorithms are...
Can entropy characterize performance of online algorithms (2001)
We focus in this work on an aspect of online computation that is not addressed by the standard competitive analysis. Namely, identifying request sequences for which non-trivial online algorithms are...
A clustering approach to solving large stochastic matching problems (2001)
In this work we focus on efficient heuristics for solving a class of stochastic planning problems that arise in a variety of business, investment, and industrial applications. The problem is best...
Efficient Methods For Computing Investment Strategies For Multi-Market Commodity Trading (2001)
This paper focuses on commodity trading. Past work has dealt mainly with single market trading problems (see Dixit & Pindyck, 1994; Hauskrecht, Pandurangan, & Upfal, 1999 and the references...
Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew S. Tomkins, Eli Upfal
The pages and hyperlinks of the World-Wide Web may be viewed as nodes and edges in a directed graph. This graph has about a billion nodes today, several billion links, and appears to grow...
Sequencing-by-Hybridization at the Information-Theory Bound: An Optimal Algorithm (2000)
Franco P. Preparata, Eli Upfal
In a recent paper (Preparata et al., 1999) we introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a...
Sequencing-by-Hybridization at the Information-Theory Bound: An Optimal Algorithm (2000)
Franco P. Preparata, Eli Upfal
In a recent paper (Preparata et al., 1999) we introduced a novel probing scheme for DNA sequencing by hybridization (SBH). The new gapped-probe scheme combines natural and universal bases in a...
Computing near optimal strategies for stochastic investment planning problems (1999)
Milos Hauskrecht, Gopal P, Eli Upfal
We present efficient techniques for computing near optimal strategies for a class of stochastic commodity trading problems modeled as Markov decision processes (MDPs). The process has a continuous...
Reducing Network Congestion and Blocking Probability Through Balanced Allocation (1999)
We compare the performance of a variant of the standard Dynamic Alternative Routing (DAR) technique commonly used in telephone and ATM networks to a path selection algorithm that is based on the...
Optimal Reconstruction of a Sequence From its Probes (1999)
Alan M. Frieze, Franco P. Preparata, Eli Upfal
An important combinatorial problem, motivated by DNA sequencing in molecular biology, is the reconstruction of a sequence over a small finite alphabet from the collection of its probes (the sequence...
Computing near optimal strategies for stochastic investment planning problems (1999)
Milos Hauskrecht, Gopal P, Eli Upfal
We present efficient techniques for computing near optimal strategies for a class of stochastic commodity trading problems modeled as Markov decision processes (MDPs). The process has a continuous...
Computing near optimal strategies for stochastic investment planning problems (1999)
Milos Hauskrecht, Gopal P, Eli Upfal
We present efficient techniques for computing near optimal strategies for a class of stochastic commodity trading problems modeled as Markov decision processes (MDPs). The process has a continuous...
Reliable fault diagnosis with few tests (1998)
We consider the problem of fault diagnosis in multiprocessor systems. Processors perform tests on one another: fault-free testers correctly identify the fault status of tested processors, while...
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
A steady state analysis of diffracting trees (1998)
Nir Shavit, Eli Upfal, Asaph Zemach
Diffracting trees are an effective and highly scalable distributed-parallel technique for shared counting and load balancing. This paper presents the first steady-state combinatorial model and...
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...
A Steady State Analysis of Diffracting Trees (Extended Abstract) (1998)
Nir Shavit, Eli Upfal, Asaph Zemach
) Nir Shavit Eli Upfal y Asaph Zemach z Abstract Diffracting trees are an effective and highly scalable distributed -parallel technique for shared counting and load balancing. This paper presents the...
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...
Optimal Construction of Edge-Disjoint Paths in Random Graphs (1998)
Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal
.<F3.823e+05> Given a graph<F3.498e+05> G<F3.823e+05> =<F3.498e+05> (V,<F3.823e+05> E) with<F3.498e+05> n<F3.823e+05> vertices,<F3.498e+05>...
A Steady State Analysis of Diffracting (1998)
Trees Nir Shavit, Nir Shavit, Eli Upfal
Diffracting trees are an effective and highly scalable distributed-parallel technique for shared counting and load balancing. This paper presents the first steady-state combinatorial model and...
Dynamic packet routing on arrays with bounded buffers (1998)
Andrei Z. Broder, Alan M. F~ieze, Eli Upfal
Abstract. We study the performance of packet routing on arrays (or meshes) with bounded buffers in the routing switches, assuming that new packets are continuously inserted at all the nodes. We give...
Efficient algorithms for all-to-all communications in multiport message-passing systems (1997)
Bruck, Jehoshua, Ho, Ching-Tien, Kipnis, Shlomo, Upfal, Eli, Weathersby, Derrick
We present efficient algorithms for two all-to-all communication operations in message-passing systems: index (or all-to-all personalized communication) and concatenation (or all-to-all broadcast)....
How to Share Memory in a Distributed System. (1997)
We study the power of shared memory in models of parallel computation. We describe a novel distributed data structure that eliminates the need for shared memory without significantly increasing the...
Web Search Using Automatic Classification (1997)
Chandra Chekuri, Michael H. Goldwasser, Prabhakar Raghavan, Eli Upfal
We study the automatic classification of Web documents into pre-specified categories, with the objective of increasing the precision of Web search. We describe experiments in which we classify...
Efficient Algorithms for All-to-All Communications in Multi-Port Message-Passing Systems (1997)
Jehoshua Bruck, Senior Member, Ching-tien Ho, Shlomo Kipnis, Eli Upfal, Senior Member, ...
Abstract—We present efficient algorithms for two all-to-all communication operations in message-passing systems: index (or all-toall personalized communication) and concatenation (or all-to-all...
Web Search Using Automatic Classification (1997)
Chandra Chekuri, Michael H. Goldwasser, Prabhakar Raghavan, Eli Upfal
We study the automatic classification of Web documents into pre-specified categories, with the objective of increasing the precision of Web search. We describe experiments in which we classify...
Static and dynamic path selection on expander graphs: a random walk approach (1997)
Andrei Z. Broder, Alan M. Frieze, Eli Upfal
This paper addresses the problem of virtual circuit switching in bounded degree expander graphs. We study the static and dynamic versions of this problem. Our solutions are based on the rapidly...
A Wait-Free Sorting Algorithm (1997)
Nir Shavit, Eli Upfal, Asaph Zemach
Sorting is one of a set of fundamental problems in computer science. In this paper we present the first wait-free algorithm for sorting an input array of size N using P N processors to achieve...
A Steady State Analysis of Diffracting Trees (1997)
Nir Shavit, Eli Upfal, Asaph Zemach
Diffracting trees are an effective and highly scalable distributed-parallel technique for shared counting and load balancing. This paper presents the first steady-state combinatorial model and...
Real-Time Communication Scheduling in a Multicomputer Video Server (1997)
In this paper, we address the problem of scheduling communication over the interconnection network of a distributed-memory multicomputer video server. We show that this problem is closely related to...
A General Approach to Dynamic Packet Routing with Bounded Buffers (1996)
Andrei Z. Broder, Alan M. Frieze, Eli Upfal
We prove a sufficient condition for the stability of dynamic packet routing algorithms. Our approach reduces the problem of steady state analysis to the easier and better understood question of...
Web Search Using Automatic Classification (1996)
Chandra Chekuri, Michael H. Goldwasser, Prabhakar Raghavan, Eli Upfal
: We study the automatic classification of Web documents into pre-specified categories, with the objective of increasing the precision of Web search. We describe experiments in which we classify...
Web Search Using Automatic Classification (1996)
Chandra Chekuri, Michael H. Goldwasser, Prabhakar Raghavan, Eli Upfal
: We study the automatic classification of Web documents into pre-specified categories, with the objective of increasing the precision of Web search. We describe experiments in which we classify...
The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height (1995)
Andrei Z. Broder, Martin E. Dyer, Alan M. Frieze, Prabhakar Raghavan, Eli Upfal
The random simplex algorithm for linear programming proceeds as follows: at each step, it moves from a vertex v of the polytope to a randomly chosen neighbor of v, the random choice being made from...
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal
Abstract. Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1...
On the Theory of Interconnection Networks for Parallel Computers (1994)
. Efficient data transfer between processors is an essential component in any large scale parallel computation. Motivated by the growing interest in parallel computers, a significant amount of...
How much can hardware help routing? (Extended Abstract) (1994)
Allan Borodin, Prabhakar Raghavan, Baruch Schieber, Eli Upfal
Allan Borodin Prabhakar Raghavan y Baruch Schieber y Eli Upfal z April 21, 1994 Abstract We study the extent to which complex hardware can speed up routing. Specifically, we consider the following...
Optimal Construction of Edge-Disjoint Paths in Random Graphs (1994)
Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal
Given a graph G = (V; E) with n vertices, and m edges, and a family of pairs of vertices in V , we are interested in finding for each pair (a i ; b i ), a path connecting a i to b i , such that the...
Efficient Routing in All-Optical Networks (1994)
Communication in all-optical networks requires novel routing paradigms. The high bandwidth of the optic fiber is utilized through wavelengthdivision multiplexing: A single physical optical link can...
Efficient Routing in All-Optical Networks (1994)
Communication in all-optical networks requires novel routing paradigms. The high bandwidth of the optic fiber is utilized through wavelengthdivision multiplexing: a single physical optical link can...
Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Eli Upfal
Suppose that we sequentially place n balls into n boxes by putting each ball into a randomly chosen box. It is well known that when we are done, the fullest box has with high probability (1 + o(1))...
Optimal construction of edge-disjoint paths in random graphs (1994)
Andrei Z. Broder, Alan M. Frieze, Stephen Suen, Eli Upfal
Abstract. Given a graph G =(V,E) with n vertices, m edges, and a family of κ pairs of vertices in V, we are interested in finding for each pair (ai,bi) a path connecting ai to bi such that the set...
A Theory of Wormhole Routing in Parallel Computers (1993)
Sergio Felperin, Prabhakar Raghavan, Eli Upfal
Virtually all theoretical work on message routing in parallel computers has dwelt on packet routing: messages are conveyed as packets, an entire packet can reside at a node of the network, and a...
Trading Space for Time in Undirected s-t Connectivity (1991)
Andrei Z. Broder, Prabhakar Raghavan, Robert W. Taylor, Anna R. Karlin, Anna R. Karlin, Eli Upfal, ...
Aleliunas et al. [1] posed the following question: "The reachability problem for undirected graphs can be solved in logspace and O.mn/ time [m is the number of edges and n is the number of...
A Simple Load Balancing Scheme for Task Allocation in Parallel Machines (1991)
Larry Rudolph, Miriam Slivkin-allalouf, Eli Upfal
A collection of local workpiles (task queues) and a simple load balancing scheme is well suited for scheduling tasks in shared memory parallel machines. Task scheduling on such machines has usually...
Trading space for time in undirected s-t connectivity (1989)
Andrei Z. Broder, Anna R. Karlin, Anna R. Karlin, Prabhakar Raghavan, Prabhakar Raghavan, ...
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
Trading space for time in undirected s-t connectivity (1989)
Andrei Z. Broder, Anna R. Karlin, Anna R. Karlin, Prabhakar Raghavan, Prabhakar Raghavan, ...
DEC’s business and technology objectives require a strong research program. The Systems Research Center (SRC) and three other research laboratories are committed to filling that need. SRC began...
Stochastic Contention Resolution With Short Delays
We study contention resolution protocols under a stochastic model of continuous request generation from a set of contenders. The performance of such a protocol is characterized by two parameters: the...
Stochastic Contention Resolution With Short Delays
Prabhakar Raghavan And, Prabhakar Raghavan, Eli Upfal
We study contention resolution protocols under a stochastic model of continuous request generation from a set of contenders. The performance of such a protocol is characterized by two parameters: the...