EDGE DISJOINT PATHS IN MODERATELY CONNECTED GRAPHS ∗ (2009)
Abstract. We study the Edge Disjoint Paths (EDP) problem in undirected graphs: Given a graph G with n nodes and a set T of pairs of terminals, connect as many terminal pairs as possible using paths...
Learning Mixtures of Product Distributions using Correlations and Independence (2009)
Kamalika Chaudhuri, Satish Rao
We study the problem of learning mixtures of distributions, a natural formalization of clustering. A mixture of distributions is a collection of distributions D = {D1,...DT}, and � mixing weights,...
Kamalika Chaudhuri, Satish Rao
We study the problem of learning mixtures of distributions, a natural formalization of clustering. A mixture of distributions is a collection of distributions D = {D1,..., DT} and weights w1,..., wT....
Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao
Modern networking applications replicate data and services widely, leading to a need for location-independent routing – the ability to route queries directly to objects using names independent of...
Theory of Computing Systems (2008)
Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao
Abstract. Modern networking applications replicate data and services widely, leading to a need for location-independent routing—the ability to route queries to objects using names independent of...
Definition. Let G be a class of graphs and let G ∈ G. A graph metric is the shortest distance metric d on the vertices V (G) of G. Definition. A planar metric is a graph metric on the class of all...
Fast phylogeny reconstruction through learning of ancestral sequences (2008)
Mihaescu, Radu, Hill, Cameron, Rao, Satish
Given natural limitations on the length DNA sequences, designing phylogenetic reconstruction methods which are reliable under limited information is a crucial endeavor. There have been two approaches...
Abstract. We study the Edge Disjoint Paths (EDP) problem in undirected graphs: Given a graph G with n nodes and a set T of pairs of terminals, connect as many terminal pairs as possible using paths...
ABSTRACT Distributed Object Location in a Dynamic Network (2008)
Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao
Modern networking applications replicate data and services widely, leading to a need for location-independent routing – the ability to route queries directly to objects using names independent of...
Edge Disjoint Paths in Moderately Connected Graphs (2008)
Abstract. We study the Edge Disjoint Paths (EDP) problem in undirected graphs: Given a graph G with n nodes and a set T of pairs of terminals, connect as many terminal pairs as possible using paths...
We present awork-optimal randomized algorithm for simulating a shared memory machine (pram) on an optical communication parallel computer (ocpc). The ocpc model is motivated by the potential of...
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows (2008)
Biswal, Punyashloka, Lee, James R., Rao, Satish
We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric...
Using Semi-Definite Programming to Enhance (2008)
Supertree Resolvability, Shlomo Moran, Satish Rao, Sagi Snir
Abstract. Supertree methods are used to construct a large tree over a large set of taxa, from a set of small trees over overlapping subsets of the complete taxa set. Since accurate reconstruction...
article no. SS971493 Faster Shortest-Path Algorithms for Planar Graphs (2008)
Monika R. Henzinger, Philip Klein, Satish Rao, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Edge Disjoint Paths in Moderately Connected Graphs (2008)
Abstract. We study the Edge Disjoint Paths (EDP) problem in undirected graphs: Given a graph G with n nodes and a set T of pairs of terminals, connect as many terminal pairs as possible using paths...
Samantha Riesenfeld, Advisor Prof, Richard M. Karp, Satish Rao, Alistair Sinclair, Dorit Hochbaum
Combinatorial optimization, algorithms, and algorithmic tools for computational biology. Also, machine learning, applied probability, metric embeddings, and networks.
Abstract Towards Efficiemlcy and Portability: Programming with the BSP Model (2008)
Mark Gouclreau, Kevin Lang, Satish Rao, Torsten Suel
The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a model for general-purpose parallel computa-tion. The objective of the model is to allow the design of parallel programs that can...
Edge Disjoint Paths in Moderately Connected Graphs (2008)
Abstract. We study the Edge Disjoint Paths (EDP) problem in undirected graphs: Given a graph G with n nodes and a set T of pairs of terminals, connect as many terminal pairs as possible using paths...
problems MINIMUM LINEAR ARRANGEMENT, (2008)
Moses Charikar, Mohammadtaghi Hajiaghayi, Satish Rao
We design approximation algorithms for the vertex ordering
An Efficient and Accurate Graph-Based Approach to Detect Population Substructure (2008)
Srinath Sridhar, Satish Rao, Eran Halperin
Abstract. Currently, large-scale projects are underway to perform whole genome disease association studies. Such studies involve the genotyping of hundreds of thousands of SNP markers. One of the...
Rajeshwari, S., Adhikari, Prabha M.R., Ramapuram, John T., Rao, Satish
Aim: To compare the safety and efficacy of low dose vs high dose of amphotericin B in cryptococcal meningitis associated with HIV infection. Materials and Methods: Retrospective data of patients...
Faster Vertex Connectivity Algorithms (2007)
Monika Rauch Henzinger, Satish Rao
We present a preflow-push algorithm for determining the vertex connectivity of an n-node, m-edge graph with positive vertex capacities. We give a deterministic algorithm that computes (u) = min v 6=u...
Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao
Modern networking applications replicate data and services widely, leading to a need for location-independent routing-- the ability to route queries directly to objects using names independent of the...
Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao
Modern networking applications replicate data and services widely, leading to a need for location-independent routing – the ability to route queries directly to objects using names independent of...
Tom Leighton, Chi-jen Lu, Satish Rao
Abstract. The Lov'asz Local Lemma (LLL) is a powerful tool that is increasingly playing a valuable role in computer science. The original lemma was nonconstructive; a breakthrough of Beck and...
Charles E. Leiserson, Satish Rao, Sivan Toledo
When a numerical computation fails to fit in the primary memory of a serial or parallel computer, a so-called "out-of-core " algorithm must be used which moves data between primary...
Expander Flows, Geometric Embeddings and Graph Partitioning (2007)
Sanjeev Arora, Satish Rao, Umesh Vazirani
We give a O( # log n)-approximation algorithm for sparsest cut, balanced separator, and graph conductance problems. This improves the O(log n)-approxi- mation of Leighton and Rao (1988). We use a...
Theory of Computing Systems (2007)
Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao
Abstract. Modern networking applications replicate data and services widely, leading to a need for location-independent routing—the ability to route queries to objects using names independent of...
Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar
In the minimum-degree minimum spanning tree (MDMST) problem, we are given a graph G, and the goal is to find a minimum spanning tree (MST) T, such that the maximum degree of T is as small as...
A rigorous analysis of population stratification with limited data (2007)
Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou
Abstract Finding the genetic factors of complex diseases such as can-cer, currently a major effort of the international community, will potentially lead to better treatment of these diseases.One of...
A rigorous analysis of population stratification with limited data (2007)
Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou
Finding the genetic factors of complex diseases such as cancer, currently a major effort of the international community, will potentially lead to better treatment of these diseases. One of the major...
A rigorous analysis of population stratification with limited data (2007)
Kamalika Chaudhuri, Eran Halperin, Satish Rao, Shuheng Zhou
Finding the genetic factors of complex diseases such as cancer, currently a major effort of the international community, will potentially lead to better treatment of these diseases. One of the major...
A push-relabel algorithm for approximating degree-bounded spanning trees (2006)
Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar
Abstract. Given a graph G and degree bound B on its nodes, the bounded-degree minimum spanning tree (BDMST) problem is to find a minimum cost spanning tree among the spanning trees with maximum...
A push-relabel algorithm for approximating degree-bounded spanning trees (2006)
Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar
Abstract. Given a graph G and degree bound B on its nodes, the bounded-degree minimum spanning tree (BDMST) problem is to find a minimum cost spanning tree among the spanning trees with maximum...
In this paper, we consider a multicommodity flow problem where for each pair of vertices, (u.v), we are required to send f half-units of commodity (u,v) from u to v and f half-units of commodity...
What would edmonds do? augmenting paths and witnesses for bounded degree msts (2005)
Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar
C, degree Bspanning tree, and parameters b, w> 1, produces a tree whose cost is at most wC and whosedegree is at most w w-1 bB + logb n.A primary contribution of K"onemann and Ravi is a...
What would edmonds do? augmenting paths and witnesses for bounded degree msts (2005)
Kamalika Chaudhuri, Satish Rao, Samantha Riesenfeld, Kunal Talwar
Given a graph and degree upper bounds on vertices, the BDMST problem requires us to find a minimum cost spanning tree respecting the given degree bounds. This problem generalizes the Travelling...
Lower Bounds for Maximum Parsimony with Gene Order Data (2005)
Abraham Bachrach, Kevin Chen, Chris Harrelson, Radu Mihaescu, Satish Rao, Apurva Shah
Abstract. In this paper, we study lower bound techniques for branchand-bound algorithms for maximum parsimony, with a focus on gene order data. We give a simple O(n 3) time dynamic programming...
Distributed object location in a dynamic network (2004)
Hildrum, Kirsten, Kubiatowicz, John D, Rao, Satish, Zhao, Ben Y
Modem networking applications replicate data and services widely, leading to a need for location-independent routing - the ability to route queries to objects using names independent of the objects'...
A note on the nearest neighbor in growth-restricted metrics (2004)
Kirsten Hildrum, John Kubiatowicz, Sean Ma, Satish Rao
In this paper, we give results relevant to sequential and distributed dynamic data structures for finding nearest neighbors in growth-restricted metrics. Our sequential data structure uses linear...
Expander flows, geometric embeddings and graph partitioning (2004)
Sanjeev Arora, Satish Rao, Umesh Vazirani
We give aO ( � logn)-approximation algorithm for sparsest cut, balanced separator, and graph conductance problems. This improves theO(logn)-approximation of Leighton and Rao (1988). We use a...
A note on the nearest neighbor in growth-restricted metrics (2004)
Kirsten Hildrum, John Kubiatowicz, Sean Ma, Satish Rao
In this paper, we give results relevant to sequential and distributed dynamic data structures for finding nearest neighbors in growth-restricted metrics. Our sequential data structure uses linear...
A tight bound on approximating arbitrary metrics by tree metrics (2003)
Jittat Fakcharoenphol, Satish Rao, Kunal Talwar
In this paper, we show that any n point metric space can be embedded into a distribution over dominating tree metrics such that the expected stretch of any edge is O(log n). This improves upon the...
An improved approximation algorithm for the 0-extension problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar
Abstract Given a graph G = (V, E), a set of terminals T ` V, anda metric D on T, the 0-extension problem is to assignvertices in V to terminals, so that the sum, over all edges e, of the distance...
Paths, trees and minimum latency tours (2003)
Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar
We give improved approximation algorithms for a variety of latency minimization problems. In particular, we give a 3.59 1-approximation to the minimum latency problem, improving on previous...
Another way to find the nearest neighbor in growth-restricted metrics (2003)
Kirsten Hildrum, John Kubiatowicz, Satish Rao
In this paper, we give sequential and distributed dynamic data structures for finding nearest neighbors in certain growth restricted metrics. In particular, we give a sequential data structure that...
A Polynomial-time Tree Decomposition to Minimize Congestion (2003)
Chris Harrelson, Kirsten Hildrum, Satish Rao
Racke recently gave a remarkable proof showing that any undirected multicommodity ow problem can be routed in an oblivious fashion with congestion that is within a factor of O(log n) of the best...
A Polynomial-time Tree Decomposition to Minimize Congestion (2003)
Chris Harrelson, Kirsten Hildrum, Satish Rao
Racke recently gave a remarkable proof showing that any undirected multicommodity ow problem can be routed in an oblivious fashion with congestion that is within a factor of O(log^3 n) of the best...
The k-Traveling Repairman Problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao
We consider the k-traveling repairman problem, a generalization of the metric traveling repairman problem, also known as the minimum latency problem, to multiple repairmen. We give an...
Another Way to Find the Nearest Neighbor in Growth-Restricted Metrics (2003)
Kirsten Hildrum, John Kubiatowicz, Satish Rao
In this paper, we give sequential and distributed dynamic data structures for finding nearest neighbors in certain growth restricted metrics.
The k-Traveling Repairman Problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao
We consider the k-traveling repairman problem, a generalization of the metric traveling repairman problem, also known as the minimum latency problem, to multiple repairmen. We give an...
An improved approximation algorithm for the 0-extension problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar
Abstract Given a graph G = (V, E), a set of terminals T ` V, anda metric D on T, the 0-extension problem is to assignvertices in V to terminals, so that the sum, over all edges e, of the distance...
Constant factor approximation of vertex-cuts in planar graphs (2003)
Eyal Amir, Robert Krauthgamer, Satish Rao
We devise the first constant factor approximation algorithm for minimum quotient vertex-cuts in planar graphs. Our algorithm achieves approximation ratio 1+ 4 (1+ǫ) with running time O(W · 3 n...
An Improved Approximation Algorithm for the 0-Extension Problem (2003)
Jittat Fakcharoenphol, Chris Harrelson, Satish Rao, Kunal Talwar
Given a graph G = (V, E), a set of terminals T V , and a metric D on T , the 0-extension problem is to assign vertices in V to terminals, so that the sum, over all edges e, of the distance (under D)...
A polynomial-time tree decomposition to minimize congestion (2003)
Chris Harrelson, Kirsten Hildrum, Satish Rao
Räcke recently gave a remarkable proof showing that any undirected multicommodity flow problem can be routed in an oblivious fashion with congestion that is within a factor of O(log 3 n) of the best...
Distributed data location in a dynamic network (2002)
Kirsten Hildrum, Kirsten Hildrum, John D. Kubiatowicz, John D. Kubiatowicz, Satish Rao, Satish Rao, ...
Modern networking applications replicate data and services widely, leading to a need for locationindependent routing-- the ability to route queries directly to objects using names that are...
Distributed data location in a dynamic network (2002)
Kirsten Hildrum, Kirsten Hildrum, John D. Kubiatowicz, John D. Kubiatowicz, Satish Rao, Satish Rao, ...
Modern networking applications replicate data and services widely, leading to a need for locationindependent routing – the ability to route queries directly to objects using names that are...
Distributed object location in a dynamic network (2002)
Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao
Modern networking applications replicate data and services widely, leading to a need for location-independent routing-- the ability to route queries to objects using names independent of the objects...
Distributed object location in a dynamic network (2002)
Kirsten Hildrum, John D. Kubiatowicz, Satish Rao, Ben Y. Zhao
Modern networking applications replicate data and services widely, leading to a need for location-independent routing-- the ability to route queries directly to objects using names independent of the...
Distributed Object Location in a Dynamic Network (2002)
Kirsten Hildrum, John Kubiatowicz, Satish Rao, Ben Y. Zhao
Modern networking applications replicate data and services widely, leading to a need for location-independent routing -- the ability to route queries to objects using names independent of the...
Ministère Recherche, Science Et Technologie, Ministère Recherche, Science Et Technologie, ...
34th ACM Symposium
Planar graphs, negative weight edges, shortest paths, and near linear time (2001)
Jittat Fakcharoenphol, Satish Rao
In this paper, we present an O(n log
Fast Approximate Graph Partitioning Algorithms (1999)
Guy Even, Joseph (Seffi) Naor, Satish Rao, Baruch Schieber
. We study graph partitioning problems on graphs with edge capacities and vertex weights. The problems of b-balanced cuts and k-balanced partitions are unified into a new problem called minimum...
Flows In Undirected Unit Capacity Networks (1999)
Andrew V. Goldberg, Satish Rao
.<F3.808e+05> We describe an<F3.485e+05><F3.808e+05><F3.485e+05> O(min(m, n<F2.756e+05><F2.512e+05><F2.756e+05> 3/2<F3.808e+05><F3.485e+05>...
A nearly linear-time approximation scheme for the Euclidean k-median problem (1999)
Stavros G. Kolliopoulos, Satish Rao
In the k-median problem we are given a set N of n points in a metric space and a positive integer k: The objective is to locate k medians among the points so that the sum of the distances from each...
Universal Packet Routing Algorithms. (1998)
Leighton, Tom, Maggs, Bruce, Rao, Satish
This paper examines the packet routing problem in a network independent context. The goal is to devise a strategy for routing that works well for a wide variety of networks. To achieve this goal, the...
Work-Preserving Emulations of Fixed-Connection Networks, (1998)
Koch, Richard, Leighton, Tom, Maggs, Bruce, Rao, Satish, Rosenberg, Arnold
In this paper, we study the problem of emulating TG steps of an NG-node guest network on an NH-node host network. Although many isolated emulation results have been proved for specific networks in...
Work-Preserving Emulations of Fixed-Connection Networks, (1998)
Koch, Richard, Leighton, Tom, Maggs, Bruce, Rao, Satish, Rosenberg, Arnold
In this paper the problem of emulating TG steps of an NG-node guest network on an NH-node host network. We call an emulation work-preserving if the time required by the host, TH, is O(TGNG/NH)...
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...
Approximation schemes for euclidean k-medians and related problems (1998)
Sanjeev Arora, Prabhakar Raghavan, Satish Rao
In the k-median problem we are given a set S of n points in a metric space and a positive integer k. We desire to locate k medians in space, such that the sum of the distances from each of the points...
Approximation schemes for Euclidean (1998)
Medians And Related, Sanjeev Arora, Prabhakar Raghavan, Satish Rao
In the k-median problem we are given a set S of n points in a metric space and a positive integer k. We desire to locate k medians in space, such that the sum of the distances from each of the points...
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...
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...
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...
Approximation algorithms for Steiner and directed multicuts (1997)
Philip N. Klein, Serge A. Plotkin, Satish Rao, Eva Tardos
In this paper we consider the steiner multicut problem. This is a generalization of the minimum multicut problem where instead of separating node pairs, the goal is to find a minimum weight set of...
Short-Length Menger Theorems (1997)
Monika Rauch Henzinger, Jon Kleinberg, Satish Rao, Let G
We give short and simple proofs of the following two theorems by Galil and Yu [3]. Let s and t be two vertices in an n-node graph G. (1) There exist k edge-disjoint s-t paths of total length O(n #...
Flows in Undirected Unit Capacity Networks (1997)
Andrew V. Goldberg, Satish Rao
We describe an O(min(m; n 3=2 )m 1=2 )-time algorithm for finding maximum flows in undirected networks with unit capacities and no parallel edges. This improves upon the previous bound of Karzanov...
Length Functions for Flow Computations (1997)
Andrew V. Goldberg, Satish Rao
We introduce a new approach to the maximum flow problem. This approach is based on assigning arc lengths based on the residual flow value and the residual arc capacities. Our approach leads to an...
Approximation Algorithms for Steiner and Directed Multicuts (1997)
Philip N. Klein, Serge A. Plotkin, Satish Rao, Eva Tardos, Éva Tardosz, Steiner Multicuts
In this paper we consider the steiner multicut problem. This is a generalization of the minimum multicut problem where instead of separating node pairs, the goal is to find a minimum weight set of...
Short-length menger theorems (1997)
Monika Rauch Henzinger, Jon Kleinberg, Satish Rao
We give short and simple proofs of the following two theorems by Galil and Yu [3]. Let s and t be two vertices in an n-node graph G. (1) There exist k edge-disjoint s-t paths of total length O(n √...
Short-length menger theorems (1997)
Monika Rauch Henzinger, Jon Kleinberg, Satish Rao
We give short and simple proofs of the following two theorems by Galil and Yu [3]. Let s and t be two vertices in an n-node graph G. (1) There exist k edge-disjoint s-t paths of total length O(n √...
Computing vertex connectivity: New bounds from old techniques (1996)
Henzinger, Monika R., Rao, Satish, Gabow, Harold N.
The vertex connectivity K of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the...
Towards Efficiency and Portability: Programming with the BSP Model (1996)
Mark Goudreau, Kevin Lang, Satish Rao, Torsten Suel, Thanasis Tsantilas
The Bulk-Synchronous Parallel (BSP) model was proposed by Valiant as a model for general-purpose parallel computation. The objective of the model is to allow the design of parallel programs that can...
Divide-and-Conquer Approximation Algorithms via Spreading Metrics (1996)
Guy Even, Joseph (Seffi) Naor, Satish Rao, Baruch Schieber
We present a novel divide-and-conquer paradigm for approximating NP-hard graph optimization problems. The paradigm models graph optimization problems that satisfy two properties: First, a...
Monika R. Henzinger, Satish Rao, Harold N. Gabow
The vertex connectivity � of a graph is the smallest number of vertices whose deletion separates the graph or makes it trivial. We present the fastest known deterministic algorithm for finding the...
Circuit Switching: A Multicommodity Flow Based Approach. (1995)
In this paper, we consider the problem of routing virtual circuits in a network. In particular, given a set of request pairs in a network, we wish to route a path between each pair so that very few...
Shallow excluded minors and improved graph decompositions (1994)
Serge Plotkin, Satish Rao, Warren D. Smith
In this paper we introduce the notion of the limited-depth minor exclusion and show that graphs that exclude small limited-depth minors have relatively small separators. In particular, we prove that...
Faster Shortest-Path Algorithms for Planar Graphs (1994)
Philip Klein Brown, Satish Rao, Monika Rauch, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edgelengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Faster Shortest-Path Algorithms for Planar Graphs (1994)
Monika R. Henzinger, Philip Klein, Satish Rao, Sairam Subramanian
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edge-lengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
Faster Shortest-Path Algorithms for Planar Graphs (1994)
Sairam Subramanian, Philip Klein, Philip Klein, Satish Rao, Satish Rao, Monika Rauch, ...
We give a linear-time algorithm for single-source shortest paths in planar graphs with nonnegative edgelengths. Our algorithm also yields a linear-time algorithm for maximum flow in a planar graph...
An Optical Simulation of Shared Memory (1994)
Leslie Ann Goldberg, Yossi Matias, Satish Rao
We present a work-optimal randomized algorithm for simulating a shared memory machine (pram) on an optical communication parallel computer (ocpc). The ocpc model is motivated by the potential of...
An Optical Simulation of Shared Memory (1994)
Leslie Ann Goldberg, Yossi Matias, Satish Rao
We present a work-optimal randomized algorithm for simulating a shared memory machine (pram) on an optical communication parallel computer (ocpc). The ocpc model is motivated by the potential of...
Shallow Excluded Minors and Improved Graph Decompositions (1994)
Serge Plotkin, Satish Rao, Warren D. Smith
In this paper we introduce the notion of the limiteddepth minor exclusion and show that graphs that exclude small limited-depth minors have relatively small separators. In particular, we prove that...
Doubly Logarithmic Communication Algorithms for Optical Communication Parallel Computers (1994)
Leslie Ann Goldberg, Mark Jerrum, Tom Leighton, Satish Rao, Tom Leighton Mit
In this paper we consider the problem of interprocessor communication on parallel computers that have optical communication networks. We consider the Completely Connected Optical Communication...
ARTICLE NO. AL960833 Approximation Algorithms for Steiner and Directed (1994)
Philip N. Klein, Serge A. Plotkin, Satish Rao, Eva Tardos
In this paper we consider the Steiner multicut problem. This is a generalization of the minimum multicut problem where instead of separating node pairs, the goal is to find a minimum weight set of...
Efficient Out-of-Core Algorithms for Linear Relaxation Using Blocking Covers (1993)
Charles E. Leiserson, Satish Rao, Sivan Toledo
When a numerical computation fails to fit in the primary memory of a serial or parallel computer, a so-called "out-of-core" algorithm, which moves data between primary and secondary...
Bounds on the Max-Flow Min-Cut Ratio for Directed Multicommodity Flows (1993)
Philip N. Klein, Serge A. Plotkin, Satish Rao, Éva Tardos, Eva Tardos, Eva Tardos
The most well-known theorem in combinatorial optimization is the classical max-flow min-cut theorem of Ford and Fulkerson. This theorem serves as the basis for deriving efficient algorithms for...
Excluded Minors, Network Decomposition, and Multicommodity Flow (1993)
Philip Klein, Serge A. Plotkin, Satish Rao
In this paper we show that, given a graph and parameters ffi and r, we can find either a Kr;r minor or an edge-cut of size O(mr=ffi) whose removal yields components of weak diameter O(r 2 ffi); i.e.,...
Approximate Load Balancing on Dynamic and Asynchronous Networks (1993)
William Aiello, Baruch Awerbuch, Bruce Maggs, Satish Rao
This paper presents a simple local algorithm for load balancing in a distributed network. The algorithm makes no assumption about the structure of the network. It can be executed on a synchronous...