Generalized Buneman pruning for inferring the most parsimonious multi-state phylogeny (2009)
Misra, Navodit, Blelloch, Guy, Ravi, R., Schwartz, Russell
Accurate reconstruction of phylogenies remains a key challenge in evolutionary biology. Most biologically plausible formulations of the problem are formally NP-hard, with no known efficient solution....
B.V. Halld'orsson y M.M. Halld'orsson z (2009)
J. K. Lenstra, R. Ravi, L. Stougie
Approximation algorithms for the test cover problem
Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice (2009)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
Abstract—We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at...
Haplotyping for Disease Association: A Combinatorial Approach (2009)
Abstract—We consider a combinatorial problem derived from haplotyping a population with respect to a genetic disease, either recessive or dominant. Given a set of individuals, partitioned into...
Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference (2009)
Srinath Sridhar, Fumei Lam, Guy E. Blelloch, R. Ravi, Russell Schwartz
Abstract—Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in...
Anupam Gupta, R. Ravi, Amitabh Sinha
Real-world networks often need to be designed under uncertainty, with only partial information and predictions of demand available at the outset of the design process. The field of stochastic...
The Directed Minimum Latency Problem (2009)
We study the directed minimum latency problem: given an n-vertex asymmetric metric (V, d) with a root vertex r ∈ V, find a spanning path originating at r that minimizes the sum of latencies at all...
Murugan, M., Shetty, P. K., Ravi, R., Subbiah, A.
Since 1895 cardamom has been cultivated in the cardamom hills of Western Ghats, India, which form a part of global biodiversity hot spots. These tropical forests in the last couple of decades have...
Hafalir, I., Ravi, R., Sayedi, A.
We study multi-unit auctions where each bidder has a private value for each unit, and a private budget which is the total amount of money she can spend. We propose a mechanism which is semi-truthful,...
Bayesian Optimal No-Deficit Mechanism Design ⋆ (2009)
Shuchi Chawla, Jason D. Hartline, R. Ravi
Abstract. One of the most fundamental problems in mechanism design is that of designing the auction that gives the optimal profit to the auctioneer. For the case that the probability distributions on...
y
Abstract An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest (2008)
A. Gupta, J. Könemann, S. Leonardi, R. Ravi, G. Schäfer
In an instance of the prize-collecting Steiner forest problem (PCSF) we are given an undirected graph G = (V,E), non-negative edge-costs c(e) for all e ∈ E, terminal pairs R = {(si,ti)}1≤i≤k,...
Bayesian Optimal No-deficit Mechanism Design? (2008)
Shuchi Chawla, Jason D. Hartline, Uday Rajan, R. Ravi
1 Introduction Suppose a seller is able to provide a service at total cost C to any number ofusers. Suppose further that the seller has done market research to determine the
General Terms Algorithms, Theory (2008)
S. Chawla, D. Kitchin, U. Rajan, R. Ravi, A. Sinha
We consider the design of multicast networks when both edges and nodes are selfish agents with private values. Given a network with a distinguished node (root) and clients at other nodes, the problem...
Approximation algorithms for minimizing (2008)
Kedar Dhamdhere, Anupam Gupta, R. Ravi
average distortion
B.V. Halld'orsson y M.M. Halld'orsson z (2008)
J. K. Lenstra, R. Ravi, L. Stougie
Approximation algorithms for the test cover problem
Worst-Case Payoffs of a Location Game (2008)
S. Chawla, U. Rajan, R. Ravi, A. Sinha
Location games model competitive placement of services such as fast-food chains, product positioning, as well as political competition. We consider a two-player, sequential location game, with n...
Approximation Algorithms for Problems Combining Facility Location and Network Design (2008)
We present approximation algorithms for integrated logistics problems that combine elements of facility location and transport network design. We first study the problem where opening facilities...
LP Rounding Approximation Algorithms for Stochastic Network Design (2008)
Anupam Gupta, R. Ravi, Amitabh Sinha
We study the Steiner tree problem and the single-cable single-sink network design problem under a two-stage stochastic model with recourse and finitely many scenarios. In these models, some edges are...
Pricing Tree Access Networks with Connected Backbones (2008)
Vineet Goyal, Anupam Gupta, Stefano Leonardi, R. Ravi
Consider the following network subscription pricing problem. We are given a graph G = (V, E) with a root r, and potential customers are companies headquartered at r with locations at a subset of...
Bayesian Optimal No-deficit Mechanism Design ⋆ (2008)
Shuchi Chawla, Jason D. Hartline, Uday Rajan, R. Ravi
Abstract. One of the most fundamental problems in mechanism design is that of designing the auction that gives the optimal profit to the auctioneer. For the case that the probability distributions on...
Antithymocyte globulin and cyclosporin in children with acquired aplastic anemia (2008)
Chandra, J, Naithani, R, Ravi, R, Singh, V, Narayan, S, Sharma, S, ...
LP Rounding Approximation Algorithms for Stochastic Network Design (2008)
Anupam Gupta, R. Ravi, Amitabh Sinha
We study the Steiner tree problem and the single-cable single-sink network design problem under a two-stage stochastic model with recourse and finitely many scenarios. In these models, some edges are...
Approximating k-cuts using Network Strength as a Lagrangean Relaxation (2008)
Given an undirected, edge-weighted connected graph, the k-cut problem is to partition the vertex set into k non-empty connected components so as to minimize the total weight of edges whose end points...
Min-Max Payoffs in a Two-Player Location Game (2008)
S. Chawla, U. Rajan, R. Ravi, A. Sinha
We consider a two-player, sequential location game in d-dimensional Euclidean space with arbitrarily distributed consumer demand. The objective for each player is to select locations so as to...
Srinath Sridhar, Guy E. Blelloch, R. Ravi, Russell Schwartz
The production of large quantities of diploid genotype data has created a need for computational methods for largescale inference of haplotypes from genotypes. One promising approach to the problem...
Abstract Line-of-Sight Networks ∗ (2008)
Alan Frieze, Jon Kleinberg, R. Ravi, Warren Debany
Random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places n points at random in a region of the plane (typically a square or circle), and then...
Minmax Payoffs of a Location Game Shuchi Chawla 1 (2008)
Uday Rajan, R. Ravi, Amitabh Sinha
Abstract We consider a two-player, sequential location game, with n stages. At each stage, players 1 and 2 choose locations from a feasible set in sequence. After all moves are made, consumers each...
y
ABSTRACT Boosted Sampling: Approximation Algorithms for Stochastic Optimization (2008)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the STEINER TREE problem, for...
Matching based augmentations for approximating connectivity problems (2008)
Abstract. We describe a very simple idea for designing approximation algorithms for connectivity problems: For a spanning tree problem, the idea is to start with the empty set of edges, and add...
High angle of Attack Forebody Flow Physics and Design Emphasizing Directional Stability (2008)
A framework for understanding the fundamental physics of flowfields over forebody type shapes at low speed, high angle of attack conditions with special emphasis on sideslip has been established....
High angle of Attack Forebody Flow Physics and Design Emphasizing Directional Stability (2008)
A framework for understanding the fundamental physics of flowfields over forebody type shapes at low speed, high angle of attack conditions with special emphasis on sideslip has been established....
Mixed Integer Linear Programming for Maximum Parsimony Phylogeny Inference (2008)
Srinath Sridhar, Fumei Lam, Guy E. Blelloch, R. Ravi, Russell Schwartz
Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in phylogeny...
Provisioning QoS in Virtual Private Network using Dynamic Scheduling (2008)
Active and programmable networks change the functionality of routers and switches by using VPN endpoints and active packets. The authors present a new packet scheduling scheme called active...
Direct maximum parsimony phylogeny reconstruction from genotype data (2007)
Sridhar, Srinath, Lam, Fumei, Blelloch, Guy E, Ravi, R, Schwartz, Russell
Abstract Background Maximum parsimony phylogenetic tree reconstruction from genetic variation data is a fundamental problem in computational genetics with many practical applications in population...
SALSA: Sequence ALignment via Steiner Ancestors (2007)
, a public--domain suite of programs for generating multiple alignments of a set of genomic sequences. We allow the use of either of the two popular objectives, Tree Alignment or Sum-of-Pairs. The...
Vineet Bafna, S. Muthukrishnan, R. Ravi
Ribonucleic acid (RNA) strings are strings over the four-letter alphabet fA; C; G;Ug with a secondary structure of base-pairing between A0U and C 0 G pairs in the string 1. Edges are drawn between...
Generalized k-Center Problems (2007)
Shiva Chaudhuri, Naveen Garg, R. Ravi
The k-center problem with triangle inequality is that of placing k center nodes in a weighted undirected graph in which the edge weights obey the triangle inequality, so that the maximum distance of...
Reconstructing Flow Paths (2007)
M. Conforti, R. Hassin, R. Ravi
For an undirected graph G = (V; E), the edge connectivity values between every pair of nodes of G can be recorded in a flow-equivalent tree that contains the edge connectivity value for a linear...
Onemann Carnegie Mellon, J. K Onemann, R. Ravi
In this paper, we present a new bicriteria approximation algorithm for the degree-bounded minimum spanning tree problem. In this problem, we are given an undirected graph, a nonnegative cost function...
Lecture Notes on Approximation Algorithms for Network Problems: Minimum Cuts (2007)
Introduction Let G = (V; E) be a connected undirected graph. Given a node set Q ` V , ffi (Q) denotes the set of all edges with one end in Q and the other end in V nQ. (Informally, ffi (Q) is the...
R. Ravi, Madhav V. Marathe, Daniel J. Rosenkrantz, S. S. Ravi
We study network-design problems with two different design objectives: the total cost of the edges and nodes in the network and the maximum degree of any node in the network. A prototypical example...
Goran Konjevod, R. Ravi, Aravind Srinivasan
The covering Steiner problem is a common generalization of the k-MST and the group Steiner problems: given an edge-weighted graph, with subsets of vertices called the groups, and a nonnegative...
Naveen Garg, Rohit Khandekar, Goran Konjevod, R. Ravi, F. S. Salman, Amitabh Sinha
Abstract. We study two versions of the single sink buy-at-bulk network design problem. We are given a network and a single sink, and several sources which demand a certain amount of ow to be routed...
R. Ravi, A. Agrawal, G. Even, J. Naor, P. Klein, S. Plotkin, ...
scheduling and interval graph completion. In Proc. ICALP '91, pages 751--762. [18] P.D. Seymour. Packing directed circuits fractionally. Combinatorica, to appear. [19] E. Tardos and V.V....
LIMITED DISTRIBUTION NOTICE (2007)
M. Dawande, J. Kalagnanam, P. Keskinocak, R. Ravi, F. S. Salman
This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its...
G. Even, N. Garg, J. Konemann, R. Ravi, A. Sinha
Abstract. A tree cover of a graph G is defined as a collection of trees such that their union includes all the vertices of G. The cost of a tree cover is the weight of the maximum weight tree in the...
Ravi, R, Prasad, YVRK, Sarma, VVS
Materials workability is one of the important aspects for any process design to achieve quality products. Identifying optimum process parameters like temperature, strain rate, and strain are normally...
Dial a Ride from k-forest (2007)
Gupta, Anupam, Hajiaghayi, MohammadTaghi, Nagarajan, Viswanath, Ravi, R.
The k-forest problem is a common generalization of both the k-MST and the dense-$k$-subgraph problems. Formally, given a metric space on $n$ vertices $V$, with $m$ demand pairs $\subseteq V \times V$...
Olsen, D.M., Rodríguez, J.A., Vranic, M., Ramaiah, V., Ravi, R., Diethrich, E., ...
Introducción. Los procedimientos endovasculares en los que se cateteriza la arteria femoral pueden complicarse con la formación de pseudoaneurismas. Recientemente se ha utilizado una técnica menos...
Ravi, R, Prasad, YVRK, Sarma, VVS
Materials workability is one of the important aspects for any process design to achieve quality products. Identifying optimum process parameters like temperature, strain rate, and strain are normally...
Alan Frieze Jon, Jon Kleinberg, R. Ravi, Warren Debany
Random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places n points at random in a region of the plane (typically a square or circle), and then...
Dial a ride from k-Forest (2007)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Viswanath Nagarajan, R. Ravi
The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a “target ”...
Alan Frieze, Jon Kleinberg, R. Ravi, Warren Debany
Random geometric graphs have been one of the fundamental models for reasoning about wireless networks: one places n points at random in a region of the plane (typically a square or circle), and then...
Efficiently finding the most parsimonious phylogenetic tree via linear programming (2007)
Srinath Sridhar, Fumei Lam, Guy E. Blelloch, R. Ravi
Abstract. Reconstruction of phylogenetic trees is a fundamental problem in computational biology. While excellent heuristic methods are available for many variants of this problem, new advances in...
Dial a ride from k-Forest (2007)
Anupam Gupta, Mohammadtaghi Hajiaghayi, Viswanath Nagarajan, R. Ravi
The k-forest problem is a common generalization of both the k-MST and the dense-k-subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V × V and a “target ”...
Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice (2007)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at most once in...
Algorithms for Analyzing Intraspecific Sequence Variation (2007)
Srinath Sridhar, Guy E. Blelloch, R. Ravi
the official policies, either expressed or implied, of any sponsoring institution, the U.S. government or any other entity
Poly-logarithmic approximation algorithms for Directed Vehicle Routing Problems (2007)
Abstract. This paper studies vehicle routing problems on asymmetric metrics. Our starting point is the directed k-TSP problem: given an asymmetric metric (V, d), a root r ∈ V and a target k ≤ |V...
Artificial neural network model for predicting stable and unstable regions in Cu-Zn alloys (2006)
Ravi, R, Prasad, YVRK, Sarma, VVS, Raidu, RS
Processing maps are developed using the Dynamic Materials Model (DMM) and instability criterion, which help in choosing optimum process parameters for hot-working of materials. Certain high-level...
Artificial neural network model for predicting stable and unstable regions in Cu-Zn alloys (2006)
Ravi, R, Prasad, YVRK, Sarma, VVS, Raidu, RS
Processing maps are developed using the Dynamic Materials Model (DMM) and instability criterion, which help in choosing optimum process parameters for hot-working of materials. Certain high-level...
Presented to The Academic Faculty (2006)
Abraham D. Flaxman, Alan Frieze, R. Ravi, Manuel Blum, Luis Von Ahn, Maverick Woo, ...
This thesis considers the average case analysis of algorithms, focusing primarily on NP-hard combinatorial optimization problems. It includes a catalog of distributions frequently used in...
Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees (2006)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
Abstract. We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at...
Minimum vehicle routing with a common deadline (2006)
Abstract. In this paper, we study the following vehicle routing problem: given n vertices in a metric space, a specified root vertex r (the depot), and a length bound D, find a minimum cardinality...
Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction (2006)
Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Srinath Sridhar
Abstract. We consider the problem of finding a Steiner minimum tree in a hypercube. Specifically, given n terminal vertices in an m dimensional cube and a parameter q, we compute the Steiner minimum...
Delegate and Conquer: An LP-based approximation algorithm for Minimum Degree MSTs (2006)
Abstract. In this paper, we study the minimum degree minimum spanning tree problem: Given a graph G = (V, E) and a non-negative cost function c on the edges, the objective is to find a minimum cost...
Daniel Golovin, Vineet Goyal, R. Ravi
Abstract. Demand-robust versions of common optimization problems were recently introduced by Dhamdhere et al. [4] motivated by the worst-case considerations of two-stage stochastic optimization...
Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees (2006)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
Abstract. We consider the problem of reconstructing near-perfect phylogenetic trees using binary character states (referred to as BNPP). A perfect phylogeny assumes that every character mutates at...
Fixed parameter tractability of binary near-perfect phylogenetic tree reconstruction (2006)
Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, Srinath Sridhar
Abstract. We consider the problem of finding a Steiner minimum tree in a hypercube. Specifically, given n terminal vertices in an m dimensional cube and a parameter q, we compute the Steiner minimum...
Daniel Golovin, Vineet Goyal, R. Ravi
Abstract. Demand-robust versions of common optimization problems were recently introduced by Dhamdhere et al. [4] motivated by the worst-case considerations of two-stage stochastic optimization...
LP Rounding Approximation Algorithms for Stochastic Network Design (2006)
Anupam Gupta, R. Ravi, Amitabh Sinha
doi 10.1287/moor.1060.0237
Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems (2005)
We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from the...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, R. Ravi, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O ( √ n)-approximation...
Finding effective support-tree preconditioners (2005)
Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan Leung, Maverick Woo
In 1995, Gremban, Miller, and Zagha introduced support-tree preconditioners and a parallel algorithm called support-tree conjugate gradient (STCG) for solving linear systems of the form Ax = b, where...
Approximation algorithms for requirement cut on graphs (2005)
In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted...
A New Algorithm for the Reconstruction of (2005)
Kedar Dhamdhere, Srinath Sridhar, Guy E. Blelloch, Eran Halperin, R. Ravi, ...
In this paper, we consider the problem of reconstructing near-perfect phylogenetic trees using binary characters. A perfect phylogeny assumes that every character mutates at most once in the...
Graph Algorithms for Planning and Partitioning (2005)
Shuchi Chawla, Anupam Gupta, R. Ravi
In this thesis, we present new approximation algorithms as well as hardness of approximation results for several planning and partitioning problems. In planning problems, one is typically given a set...
Approximation Algorithms for Low-Distortion Embeddings Into (2005)
Mihai Bădoiu, Kedar Dhamdhere, Anupam Gupta, Yuri Rabinovich, Harald Räcke, ...
We present several approximation algorithms for the problem of embedding metric spaces into a line, and into the two-dimensional plane. Among other results, we give an O( # n)-approximation algorithm...
Finding Effective Support-Tree Preconditioners (2005)
Bruce Maggs Computer, Bruce M. Maggs, R. Ravi
In 1995, Gremban, Miller, and Zagha introduced supporttree preconditioners and a parallel algorithm called supporttree conjugate gradient (STCG) for solving linear systems of the form Ax = b, where A...
Graph Algorithms for Planning and Partitioning (2005)
Shuchi Chawla, Anupam Gupta, R. Ravi
official policies, either expressed or implied, of any sponsoring institution, the U.S. government or any other entity.
On two-stage stochastic minimum spanning trees (2005)
Kedar Dhamdhere, R. Ravi, Mohit Singh
Abstract. We consider the undirected minimum spanning tree problem in a stochastic optimization setting. For the two-stage stochastic optimization formulation with finite scenarios, a simple...
Finding effective support-tree preconditioners (2005)
preconditioners and a parallel algorithm called supporttree conjugate gradient (STCG) for solving linear systems of the form Ax = b, whereA is an n × n Laplacian matrix. A Laplacian is a symmetric...
A New Algorithm for the Reconstruction of Near-Perfect Binary Phylogenetic Trees (2005)
Kedar Dhamdhere, Srinath Sridhar, Guy E. Blelloch, Eran Halperin, R. Ravi, Russell Schwartz
In this paper, we consider the problem of reconstructing near-perfect phylogenetic trees using binary characters. A perfect phylogeny assumes that every character mutates at most once in the...
How to pay, come what may: Approximation algorithms for demand-robust covering problems (2005)
Kedar Dhamdhere, Vineet Goyal, Mohit Singh, R. Ravi
Robust optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worstcase among the various...
Finding effective support-tree preconditioners (2005)
preconditioners and a parallel algorithm called supporttree conjugate gradient (STCG) for solving linear systems of the form Ax = b, whereA is an n × n Laplacian matrix. A Laplacian is a symmetric...
Approximation algorithms for requirement cut on graphs (2005)
In this paper, we unify several graph partitioning problems including multicut, multiway cut, and k-cut, into a single problem. The input to the requirement cut problem is an undirected edge-weighted...
What about Wednesday? approximation algorithms for multistage stochastic optimization (2005)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Abstract. The field of stochastic optimization studies decision making under uncertainty, when only probabilistic information about the future is available. Finding approximate solutions to...
Hedging uncertainty: Approximation algorithms for stochastic optimization problems (2004)
We initiate the design of approximation algorithms for stochastic combinatorial optimization problems; we formulate the problems in the framework of two-stage stochastic optimization, and provide...
Min-Max tree covers of graphs (2004)
G. Even, N. Garg, J. Könemann, R. Ravi, A. Sinha
We provide constant factor approximation algorithms for covering the nodes of a graph using trees (rooted or unrooted), under the objective function of minimizing the weight of the maximum weight...
Approximation algorithms for finding low-degree subgraphs (2004)
Philip N. Klein, Radha Krishnan, Balaji Raghavachari, R. Ravi
We give quasipolynomial-time approximation algorithms for designing networks with a minimum degree. Using our methods, one can design networks whose connectivity is specified by “proper ”...
Hedging uncertainty: Approximation algorithms for stochastic optimization problems (2004)
We initiate the design of approximation algorithms for stochastic combinatorial optimization problems; we formulate the problems in the framework of two-stage stochastic optimization, and provide...
Hedging uncertainty: Approximation algorithms for stochastic optimization problems (2004)
Abstract. We study the design of approximation algorithms for stochastic combinatorial optimization problems. We formulate the problems in the framework of two-stage stochastic optimization, and...
Evaluation of the Haplotype Motif Model using the Principle of Minimum Description (2004)
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, R. Ravi, Russell Schwartz
length We apply minimum description length (MDL) principles to evaluate the merit of relaxing the rigidity of block models of haplotype structure. We accomplish this by developing an MDL formulation...
Boosted sampling: Approximation algorithms for stochastic optimization (2004)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. For example, in the STEINER TREE...
Approximation algorithms for minimizing average distortion (2004)
Kedar Dhamdhere, Anupam Gupta, R. Ravi
Abstract This paper considers embeddings f of arbitrary finite metrics into the line metric! so thatnone of the distances is shrunk by the embedding f; the quantity of interest is the factor by...
Hedging uncertainty: Approximation algorithms for stochastic optimization problems (2004)
Abstract. We study two-stage, finite-scenario stochastic versions of several combinatorial optimization problems, and provide nearly tight approximation algorithms for them. Our problems range from...
A.: Boosted sampling: Approximation algorithms for stochastic optimization problems (2004)
Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the STEINER TREE problem, for...
Ravi, R, Prasad, YVRK, Sarma, VVS
Most of the time (and cost) involved in planning hot forging process is related to activities strongly dependent on human expertise, intuition, and creativity, and also to iterative procedure...
Ravi, R, Prasad, YVRK, Sarma, VVS
Most of the time (and cost) involved in planning hot forging process is related to activities strongly dependent on human expertise, intuition, and creativity, and also to iterative procedure...
Approximating Average Distortion of Embeddings into Line (2003)
elative #. vs Relative Bounds Absolute Bounds Best guarantee about "worst case" distortion. Guarantee on distortion is independent of input metric. Relative Bound Given, as input, a finite...
Algorithms for Flow Time Scheduling (2003)
Bruce Maggs, Kirk Pruhs, R. Ravi, Nikhil Bansal, Nikhil Bansal
We study scheduling algorithms for problems arising in client-server systems. In the client-server setting, there are multiple clients that submit requests for service to the server(s) over time....
Minmax Payoffs of a Location Game (2003)
Shuchi Chawla, Uday Rajan, R. Ravi, Amitabh Sinha
We consider a two-player, sequential location game, with n stages. At each stage, players 1 and 2 choose locations from a feasible set in sequence. After all moves are made, consumers each purchase...
Min-Max Payoffs of a Location Game (2003)
Shuchi Chawla, Uday Rajan, R. Ravi, Amitabh Sinha
We consider a two-player, sequential location game, with n stages. At each stage, players 1 and 2 choose locations from a feasible set in sequence. After all moves are made, consumers each purchase...
Boosted Sampling: Approximation Algorithms for Stochastic Optimization (2003)
Anupam Gupta, Martin Pal, R. Ravi, Amitabh Sinha
Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. For example, in the STEINER TREE...
Design and evaluation of propranolol hydrochloride buccal films (2002)
Raghuraman, S, Velrajan, G, Ravi, R, Jeyabalan, B, Johnson, D, Sankar, V
Solving symmetric diagonally-dominant systems by preconditioning. Unpublished manuscript (2002)
Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan Leung, Maverick Woo
In this paper we design support-tree preconditioners for n × n matrices with m nonzeros that are symmetric and diagonally-dominant with a nonnegative diagonal (SDD matrix). This reduces to designing...
Profit Maximizing Mechanisms for the Extended Multicasting Game (2002)
Shuchi Chawla, David Kitchin, Uday Rajan, R. Ravi, Amitabh Sinha
We consider the design of multicast networks when both edges and nodes are selfish agents. Our objective is a budget-balanced, strategy-proof mechanism which selects the set of clients to receive...
A.: Profit maximizing mechanisms for the extended multicasting games (2002)
Shuchi Chawla, David Kitchin, Uday Rajan, R. Ravi, Amitabh Sinha
We consider the design of multicast networks when both edges and nodes are selfish agents. Our objective is a budget-balanced, strategy-proof mechanism which selects the set of clients to receive...
Solving Symmetric Diagonally-Dominant Systems by Preconditioning (2002)
Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan Leung
In this paper we show how to find a support-tree preconditioner for any Laplacian matrix A, i.e., any matrix that can be viewed as the weighted adjacency matrix of an undirected graph G with...
Randomized approximation algorithms for query optimization problems on two processors (2002)
Eduardo Laber, Ojas Parekh, R. Ravi
Abstract. Query optimization problems for expensive predicates have received much attention in the database community. In these situations, the output to the database query is a set of tuples that...
Approximation algorithms for degree-constrained minimum-cost network-design problems (2001)
R. Ravi, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz
We study network-design problems with two different design objectives: the total cost of the edges and nodes in the network and the maximum degree of any node in the network. A prototypical example...
Naveen Garg, Rohit Khandekar, Goran Konjevod, R. Ravi, F. S. Salman, Amitabh Sinha
We study two versions of the single sink buy-at-bulk network design problem. We are given a network and a single sink, and several sources which demand a certain amount of ow to be routed to the...
given an undirected graph and values rij for each pair of vertices i and j,find a minimum-cost set of edges such that there are rij vertex-disjoint paths between ver-tices i and j. We gave...
Approximation algorithms for a capacitated network design problem (2000)
R. Hassin, R. Ravi, F. S. Salman
s2candrew. cmu. edu Abstract. We study a network loading problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to...
In this paper, we present a new bicriteria approximation algorithm for the degreebounded minimum spanning tree problem. In this problem, we are given an undirected graph, a nonnegative cost function...
In this paper, we present a new bicriteria approximation algorithm for the degreebounded minimum spanning tree problem. In this problem, we are given an undirected graph, a nonnegative cost function...
An Approximation Algorithm for the Covering Steiner Problem (2000)
The covering Steiner tree problem is a common generalization of the k-MST and the group Steiner problems: Given an edge weighted graph, with subsets of vertices called the groups, and a requirement...
On 2-Coverings and 2-Packings of Laminar Families (1999)
Joseph Cheriyan, Tibor Jordán, R. Ravi
. Let H be a laminar family of subsets of a groundset V . A k-cover of H is a multiset C of edges on V such that for every subset S in H, C has at least k edges that have exactly one end in S. A...
On 2-Coverings and 2-Packings of Laminar Families (1999)
Cheriyan Jord'an Ravi, J. Cheriyan, R. Ravi
Let H be a laminar family of subsets of a groundset V . A k-cover of H is a multiset of edges, C, such that for every subset S in H, C has at least k edges (counting multiplicities) that have exactly...
GESTALT: Genomic Steiner Alignments (1999)
. We describe GESTALT (GEnomic sequences STeiner ALignmenT) , a public{domain suite of programs for generating multiple alignments of a set of biosequences. We allow the use of either of the two...
. The traveling purchaser problem is a generalization of the traveling salesman problem with applications in a wide range of areas including network design and scheduling. The input consists of a set...
Approximation Algorithms for a Capacitated Network Design Problem (1999)
R. Hassin, R. Ravi, F. S. Salman
We study a network loading problem with applications in local access network design. Given a network, the problem is to route flow from several sources to a sink and to install capacity on the edges...
On 2-Coverings and 2-Packings of Laminar Families (1999)
J. Cheriyan, T. Jordán, R. Ravi
Let H be a laminar family of subsets of a groundset V . A k-cover of H is a multiset of edges, C, such that for every subset S in H, C has at least k edges (counting multiplicities) that have exactly...
Improving minimum cost spanning trees by upgrading nodes (1999)
S. O. Krumke, M. V. Marathe, R. Sundaram, H. Noltemeier, R. Ravi, ...
We study budget constrained network upgrading problems. We are given an undirected edge weighted graph ¦¨§�©������� � where node ���� � can be upgraded at a cost of...
C.Y.: A polynomial-time approximation scheme for minimum routing cost spanning trees (1999)
Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-mao Chao, R. Ravi, ...
Abstract. Given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair...
Bicriteria Network Design Problems (1998)
Marathe, Madhav V., Ravi, R., Sundaram, Ravi, Ravi, S. S., Rosenkrantz, Daniel J., Hunt III, Harry B.
We study a general class of bicriteria network design problems. A generic problem in this class is as follows: Given an undirected graph and two minimization objectives (under different cost...
A polylogarithmic approximation algorithm for the group Steiner tree problem (1998)
Naveen Garg, Goran Konjevod, R. Ravi
The group Steiner tree problem is a generalization of the Steiner tree problem where we ae given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight...
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems (1998)
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala
We present simple semi-definite programming relaxations for the NP-hard minimum bandwidth and minimum length linear ordering problems. We then show how these relaxations can be rounded in a natural...
A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees (1998)
Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, Chuan Yi Tang
Given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair in the...
J. Cheriyan, C Flj. Cheriyan, R. Ravi, Basic Graph Theory
Contents 1 Basic Graph Theory and Algorithms 7 1.1 Graph theory terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 The running time of algorithms . . . . . . . . . ....
Approximating Maximum Leaf Spanning Trees in Almost Linear Time (1998)
Given an undirected graph, finding a spanning tree of the graph with maximum number of leaves is MAX SNP-complete. In this paper we give a new greedy 3-approximation algorithm for maximum-leaf...
The p-Neighbor k-Center Problem (1998)
Shiva Chaudhuri, Naveen Garg, R. Ravi
The k-center problem with triangle inequality is that of placing k center nodes in a weighted undirected graph in which the edge weights obey the triangle inequality, so that the maximum distance of...
A New Bound for the 2-Edge Connected Subgraph Problem (1998)
. Given a complete undirected graph with non-negative costs on the edges, the 2-Edge Connected Subgraph Problem consists in finding the minimum cost spanning 2-edge connected subgraph (where...
A Polynomial Time Approximation Scheme for Minimum Routing Cost Spanning Trees (1998)
Bang Ye Wu, Giuseppe Lancia, Vineet Bafna, Kun-Mao Chao, R. Ravi, Chuan Yi Tang
Given an undirected graph with nonnegative costs on the edges, the routing cost of any of its spanning trees is the sum over all pairs of vertices of the cost of the path between the pair in the...
A polylogarithmic approximation algorithm for the group Steiner tree problem (1998)
Naveen Garg, Goran Konjevod, R. Ravi
Given a weighted graph with some subsets of vertices called groups, the group Steiner tree problem is to nd a minimum-weight subgraph which contains at least one vertex from each group. We give a...
Approximation Algorithms for Network Problems (1998)
Contents 1 Basic Graph Theory and Shortest-Paths Algorithms 1 1.1 Graph theory terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 The running time of algorithms . . ....
A polylogarithmic approximation algorithm for the group Steiner tree problem (1998)
Naveen Garg, Goran Konjevod, R. Ravi
The group Steiner tree problem is a generalization of the Steiner tree problem where we are given several subsets (groups) of vertices in a weighted graph, and the goal is to find a minimum-weight...
Flow Improvement and Network Flows with Fixed Costs (1998)
S.O. Krumke, H. Noltemeier, S. Schwarz, R. Ravi
this paper are NP-hard to solve. We present various approximation algorithms for the problems under study.
Approximation Algorithms for Certain Network Improvement Problems (1998)
Sven O. Krumke, Madhav V. Marathe, R. Ravi, S. S. Ravi
. We study budget constrained network upgrading problems. Such problems aim at nding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an...
Approximation Algorithms for Certain Network Improvement Problems (1998)
Sven Krumke Krumke, Madhav V. Marathe, R. Ravi, S. S. Ravi
. We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given...
Approximating the Single-Sink Link Installation Problem in Network Design (1998)
F. S. Salman, J. Cheriyan, R. Ravi, S. Subramanian
We initiate the algorithmic study of an important but NP-hard problem that arises commonly in network design. The input consists of (1) An undirected graph with one sink node and multiple source...
Approximation Algorithms for Multiple Sequence Alignment Under a Fixed Evolutionary Tree (1998)
We consider the problem of multiple sequence alignment under a fixed evolutionary tree: given a tree whose leaves are labeled by sequences, find ancestral sequences to label its internal nodes so as...
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems (1998)
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala
We present simple semi-definite programming relaxations for the NP-hard minimum bandwidth and minimum length linear ordering problems. We then show how these relaxations can be rounded in a natural...
Approximation Algorithms for Certain Network Improvement Problems (1998)
Sven O. Krumke, Madhav V. Marathe, R. Ravi, S. S. Ravi
We study budget constrained network upgrading problems. Such problems aim at finding optimal strategies for improving a network under some cost measure subject to certain budget constraints. Given an...
Parallelizing and De-parallelizing Elimination Orders (1998)
Claudson Ferreira Bornstein, Bruce M. Maggs, Gary L. Miller, R. Ravi
interval graphs, graph theory The order in which the variables of a linear system are processed determines the total amounts of fill and work to perform LU decomposition on the system. We identify a...
Parallelizing and De-parallelizing Elimination Orders (1998)
Claudson Ferreira Bornstein, Bruce M. Maggs, Gary L. Miller, R. Ravi, John Gilbert, Xerox Parc
interval graphs, graph theory The order in which the variables of a linear system are processed determines the total amounts of fill and work to perform LU decomposition on the system. We identify a...
M. Janssens, F. Catthoor, H. De Man, A Specification Invariant, P. Stelling, C. U. Martel, ...
technique for operation cost minimization in flow–graphs, ” in Proc. 7th Int. Symp. High-Level Synthesis, 1994, pp. 146–151. [9] , “A specification invariant technique for regularity...
Parallel Gaussian Elimination with Linear Work and Fill, (1997)
Bornstein, Claudson, Maggs, Bruce, Miller, Gary, Ravi, R.
This paper presents an algorithm for finding parallel elimination orderings for Gaussian elimination. Viewing a system of equations as a graphs, the algorithm can be applied directly to interval...
On Approximating Planar Metrics by Tree Metrics (1997)
Goran Konjevod, R. Ravi, F. Sibel Salmani
We connect the results of Bartal [4] on probabilistic approximation of metric spaces by tree metrics, and Klein, Plotkin and Rao [11] on decompositions of graphs without small Ks,s minors (such as...
Improving Spanning Trees by Upgrading Nodes (1997)
S. O. Krumke, M. V. Marathe, H. Noltemeir, S. Ravi, Sven O. Krumke, Hartmut Noltemeier, ...
contract W-7405-ENG-36. By acceptance of this article, the publisher recognizes that the U.S. Government retains a non-exclusive, royalty-free license to publish or reproduce the published form of...
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems (1997)
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala
We present simple semi-definite programming relaxations for the NP-hard minimum bandwidth and minimum length linear ordering problems. We then show how these relaxations can be rounded in a natural...
Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems (1997)
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala
We present simple semi-definite programming relaxations for the NP-hard minimum bandwidth and minimum length linear ordering problems. We then show how these relaxations can be rounded in a natural...
Parallelizing Elimination Orders with Linear Fill (1997)
Claudson Bornstein, Bruce Maggs, Gary Miller, R. Ravi
This paper presents an algorithm for finding parallel elimination orders for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval graphs...
On Approximating Planar Metrics by Tree Metrics (1997)
Goran Konjevod, R. Ravi, F. Sibel Salman
We connect the results of Bartal [4] on probabilistic approximation of metric spaces by tree metrics, and Klein, Plotkin and Rao [11] on decompositions of graphs without small K s;s minors (such as...
Banishing Bias from Consensus Sequences (1997)
Amir Ben-Dor, Jennifer Perone, R. Ravi
. With the exploding size of genome databases, it is becoming increasingly important to devise search procedures that extract relevant information from them. One such procedure is particularly...
Parallel Gaussian Elimination with Linear Work and Fill (1997)
Claudson Bornstein, Bruce Maggs, Gary Miller, R. Ravi
This paper presents an algorithm for finding parallel elimination orderings for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval...
Parallel Gaussian Elimination with Linear Work and Fill (1997)
Claudson Bornstein Bruce, Bruce Maggs, Gary Miller, R. Ravi
This paper presents an algorithm for finding parallel elimination orderings for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval...
Approximating the Single-Sink Edge Installation Problem in Network Design (1997)
F. S. Salman, J. Cheriyan, R. Ravi, S. Subramanian
We initiate the algorithmic study of an important but NP-hard problem that arises commonly in network design. The input consists of (1) An undirected graph with one sink node and multiple source...
Improving Steiner Trees of a Network Under Multiple Constraints (Extended Abstract) (1997)
S.O. Krumke, H. Noltemeier, M. V. Marathe, R. Ravi, S. S. Ravi
) S.O. Krumke 1 H. Noltemeier 1 M.V. Marathe 2 R. Ravi 3 S.S. Ravi 4 January 22, 1997 Abstract We consider the problem of decreasing the edge weights of a given network so that the modified network...
Banishing Bias from Consensus Sequences (1997)
Amir Ben-Dor, Giuseppe Lancia, Jennifer Perone, R. Ravi
. With the exploding size of genome databases, it is becoming increasingly important to devise search procedures that extract relevant information from them. One such procedure is particularly...
A Short Course in Computational Molecular Biology (1997)
D. Durand, M. Farach, R. Ravi, M. Singh
The advent of recombinant DNA technology during the 1970s has led to an inundation of biological sequence data. The compilation and analysis of DNA and protein sequences is now a fundamental task in...
A New Bound for the 2-Edge Connected Subgraph Problem (1997)
Given a complete graph with non-negative costs on the edges, the 2-Edge Connected Subgraph Problem consists in finding the minimum cost spanning 2-edge connected subgraph (where multiedges are...
An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems (1997)
We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has certain vertex-connectivity properties. In the survivable network design...
A Near-linear-time Approximation Algorithm for Maximum-leaf Spanning Tree (1996)
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is not only NP-complete [11] but also MAX SNP-complete [10]. The approximation ratio of the previously best...
The Constrained Minimum Spanning Tree Problem (Extended Abstract) (1996)
) R. Ravi M. X. Goemans y Abstract Given an undirected graph with two different nonnegative costs associated with every edge e (say, w e for the weight and l e for the length of edge e) and a budget...
The Power of Local Optimization: Approximation Algorithms for Maximum-leaf Spanning Tree (1996)
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is NP-complete. We use the simple technique of local optimization to provide the first approximation algorithms...
A Constant-factor Approximation Algorithm for the k-MST Problem (Extended Abstract) (1996)
Avrim Blum, R. Ravi, Santosh Vempala
) Avrim Blum R. Ravi y Santosh Vempala z Abstract Given an undirected graph with non-negative edge costs and an integer k, the k-MST problem is that of finding a tree of minimum cost on k nodes. This...
A Near-linear-time Approximation Algorithm for Maximum-leaf Spanning Tree (1996)
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is not only NP-complete [11] but also MAX SNP-complete [10]. The approximation ratio of the previously best...
A Constant-factor Approximation Algorithm for the k-MST Problem (1996)
Avrim Blum, R. Ravi, Santosh Vempala
Given an undirected graph with non-negative edge costs and an integer k, the k-MST problem is that of finding a tree of minimum cost on k nodes. This problem is known to be NP-hard. We present a...
Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles) (1996)
Vineet Bafna, Babu Narayanan, R. Ravi
We consider the following problem motivated by an application in computational molecular biology. We are given a set of weighted axis-parallel rectangles such that for any pair of rectangles and...
Service-Constrained Network Design Problems (1996)
Madhav V. Marathe, R. Ravi, Ravi Sundaram
. Several practical instances of network design problems often require the network to satisfy multiple constraints. In this paper, we focus on the following problem (and its variants): find a...
Computing similarity between RNA strings (1996)
V. Bafna, S. Muthukrishnan, R. Ravi
Ribonucleic acid (RNA) strings are strings over the four-letter alphabet fA; C; G; Ug with a secondary structure of base-pairing between A0U and C 0G pairs in the string. Edges are drawn between two...
Bicriteria Network Design Problems (1995)
Madhav Marathe Ravi, R. Ravi, Ravi Sundaram, S. S. Ravi, Daniel J. Rosenkrantz
We study a general class of bicriteria network design problems. A generic problem in this class is as follows: Given an undirected graph and two minimization objectives (under different cost...
Design Strategies for Optimal Multiplier Circuits (1995)
Charles Martel, Vojin Oklobdzija, R. Ravi, Paul F. Stelling
We present new design and analysis techniques for the synthesis of fast parallel multiplier circuits. In [4], Oklobdzija, Villeger, and Lui suggested a new approach, the Three Dimensional Method...
Approximation Algorithms for Multiple Sequence Alignment Under a Fixed Evolutionary Tree (1995)
. We consider the problem of aligning sequences related by a given evolutionary tree: given a fixed tree with its leaves labeled with sequences, find ancestral sequences to label the internal nodes...
Nonoverlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles) (1995)
Vineet Bafna, Babu Narayanan, R. Ravi
We consider the following problem motivated by an application in computational molecular biology. We are given a set of weighted axis-parallel rectangles such that for any pair of rectangles and...
Of mice and men: Algorithms for evolutionary distances between genomes with translocation (1995)
A new and largely unexplored area of computational biology is combinatorial algorithms for genome rearrangement. In the course of its evolution, the genome of an organism mutates by processes that...
Spanning trees short or small (1994)
Ravi, R., Sundaram, R., Marathe, Madhav V., Ravi, S. S., Rosenkrantz, Daniel J.
We study the problem of finding small trees. Classical network design problems are considered with the additional constraint that only a specified number $k$ of nodes are required to be connected in...
Ajit Agrawal, Ajit Agrawal, Philip Klein, Philip Klein, R. Ravi, R. Ravi
We give the first approximation algorithm for the generalized network Steiner problem, a problem in network design. An instance consists of a network with link-costs and, for each pair fi; jg of...
A nearly best-possible approximation algorithm for node-weighted Steiner trees (1993)
Philip Klein, Philip Klein, R. Ravi, R. Ravi
We give the first approximation algorithm for the node-weighted Steiner tree problem. Its performance guarantee is within a constant factor of the best possible unless ~ P ' NP . Our algorithm...
A primal-dual approximation algorithm for the Steiner forest problem (1993)
Given an undirected graph with nonnegative edge-costs, a subset of nodes of size k called the terminals, and an integer q between 1 and k, the minimum q-Steiner forest problem is to find a forest of...
R. Ravi, R. Ravi, Philip Klein, Philip Klein
We present a general approximation technique for a class of network design problems where we seek a network of minimum cost that satisfies certain communication requirements and is resilient to...
Normalized coprime factorizations for linear time-varying systems (1992)
Ravi, R., Pascoal, A. M., Khargonekar, P. P.
In this paper we show that a finite dimensional linear time-varying continuous-time system admits normalized coprime factorizations if and only if it admits a stabilizable and detectable realization....
Approximation algorithms for finding low-degree subgraphs (1992)
Philip N. Klein, Radha Krishnan, Balaji Raghavachari, R. Ravi
The Power of Local Optimization: Approximation Algorithms for Maximum-Leaf Spanning Tree (1992)
Given an undirected graph G, finding a spanning tree of G with the maximum number of leaves is NP-complete [5]. We use the simple technique of local optimization to provide the first approximation...
Approximation algorithms for Steiner augmentations for two-connectivity (1992)
We consider the problem of increasing the connectivity of a given graph to two at optimal cost. Fredrickson and Ja'Ja' [6] showed that that this problem is NP-hard and provided...
Computation of plane jet impingement on a plate (1986)
The problem of normal impingement of a laminar plane jet' on a plate has been studied by solving the Navier-Stokes equations numerically. The study was undertaken t o make a ' comparative study...
An apparatus for the study of switching characteristics in ferroelectrics (1980)
Ravi, R, Sangunni, KS, Narayanan, PS
A circuit capable of producing bipolar square pulses of voltages up to +or-400 V, employing an integrated circuit timer and two mercury wetted relays is described. The frequency of the pulses can be...
Direct maximum parsimony phylogeny reconstruction from genotype data
Sridhar, Srinath, Lam, Fumei, Blelloch, Guy E, Ravi, R, Schwartz, Russell
Isa E. Hafalir, Sayedi Amin, R. Ravi
Motivated by sponsored search auctions with hard budget constraints given by the advertisers, we study multi-unit auctions of a single item. An important example is a sponsored result slot for a...