Loading [MathJax]/extensions/MathMenu.js
R. Ravi - IEEE Xplore Author Profile
Subscribe
ADVANCED SEARCH

Author details

< Back

R. Ravi

Publications
16
Citations
311
Publications by Year
19942024
Co-Authors:
Show All Co-Authors (29)
Image of author R. Ravi

R. Ravi

Affiliation

Carnegie Mellon University

Publication Topics

Biography

R. Ravi received the BTech degree in computer science and engineering from the Indian Institute of Technology, Madras, in 1989 and the PhD degree in computer science from Brown University in 1993. After postdoctoral fellowships at the University of California, Davis, and the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS) at Princeton University, he joined the Operations Research Faculty in the Tepper School of Business at Carnegie Mellon University in 1995, where he is currently a Carnegie Bosch professor of operations research and computer science.(Based on document published on 12 November 2007).
Publications
16
Citations
311
Publications by Year
19942024
Co-Authors:
Show All Co-Authors (29)
Author's Published Works

Showing 1-16 of 16 results

  • Sort

Filter Results

Show

Sort By

Results

HITSnDIFFs: From Truth Discovery to Ability Discovery by Recovering Matrices with the Consecutive Ones Property

Zixuan Chen;Subhodeep Mitra;R. Ravi;Wolfgang Gatterbauer

2024 IEEE 40th International Conference on Data Engineering (ICDE)
Year: 2024 | Conference Paper |
We analyze a general problem in a crowd-sourced setting where one user asks a question (also called item) and other users return answers (also called labels) for this question. Different from existing crowd sourcing work which focuses on finding the most appropriate label for the question (the “truth”), our problem is to determine a ranking of the users based on their ability to answer questions. ...Show More

HITSnDIFFs: From Truth Discovery to Ability Discovery by Recovering Matrices with the Consecutive Ones Property

Zixuan Chen;Subhodeep Mitra;R. Ravi;Wolfgang Gatterbauer

Year: 2024 | Conference Paper |

Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions

Nikhil Chandak;Kenny Chour;Sivakumar Rathinam;R. Ravi

IEEE Transactions on Automation Science and Engineering
Year: 2024 | Volume: 21, Issue: 4 | Journal Article |
We interleave sampling based motion planning methods with pruning ideas from minimum spanning tree algorithms to develop a new approach for solving a Multi-Goal Path Finding (MGPF) problem in high dimensional spaces. The approach alternates between sampling points from selected regions in the search space and de-emphasizing regions that may not lead to good solutions for MGPF. Our approach provide...Show More

Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions

Nikhil Chandak;Kenny Chour;Sivakumar Rathinam;R. Ravi

Year: 2024 | Volume: 21, Issue: 4 | Journal Article |

Coalescent-Based Method for Learning Parameters of Admixture Events from Large-Scale Genetic Variation Data

Ming-Chi Tsai;Guy Blelloch;R. Ravi;Russell Schwartz

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Year: 2013 | Volume: 10, Issue: 5 | Journal Article |
Detecting and quantifying the timing and the genetic contributions of parental populations to a hybrid population is an important but challenging problem in reconstructing evolutionary histories from genetic variation data. With the advent of high throughput genotyping technologies, new methods suitable for large-scale data are especially needed. Furthermore, existing methods typically assume the ...Show More

Coalescent-Based Method for Learning Parameters of Admixture Events from Large-Scale Genetic Variation Data

Ming-Chi Tsai;Guy Blelloch;R. Ravi;Russell Schwartz

Year: 2013 | Volume: 10, Issue: 5 | Journal Article |

Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design

Takuro Fukunaga;R. Ravi

2012 IEEE 53rd Annual Symposium on Foundations of Computer Science
Year: 2012 | Conference Paper |
Cited by: Papers (7)
We consider the problem of finding a minimum edge cost subgraph of an undirected or a directed graph satisfying given connectivity requirements and degree bounds b(·) on nodes. We present an iterative rounding algorithm for this problem. When the graph is undirected and the connectivity requirements are on the element-connectivity with maximum value k, our algorithm computes a solution that is an ...Show More

Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design

Takuro Fukunaga;R. Ravi

Year: 2012 | Conference Paper |

Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

Anupam Gupta;Ravishankar Krishnaswamy;Marco Molinaro;R. Ravi

2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
Year: 2011 | Conference Paper |
Cited by: Papers (29)
In the stochastic knapsack problem, we are given a knapsack of size B, and a set of items whose sizes and rewards are drawn from a known probability distribution. To know the actual size and reward we have to schedule the item-when it completes, we get to know these values. The goal is to schedule the items (possibly making adaptive decisions based on the sizes seen so far) to maximize the expecte...Show More

Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

Anupam Gupta;Ravishankar Krishnaswamy;Marco Molinaro;R. Ravi

Year: 2011 | Conference Paper |

A Consensus Tree Approach for Reconstructing Human Evolutionary History and Detecting Population Substructure

Ming-Chi Tsai;Guy E. Blelloch;R. Ravi;Russell Schwartz

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Year: 2011 | Volume: 8, Issue: 4 | Journal Article |
Cited by: Papers (3)
The random accumulation of variations in the human genome over time implicitly encodes a history of how human populations have arisen, dispersed, and intermixed since we emerged as a species. Reconstructing that history is a challenging computational and statistical problem but has important applications both to basic research and to the discovery of genotype-phenotype correlations. We present a n...Show More

A Consensus Tree Approach for Reconstructing Human Evolutionary History and Detecting Population Substructure

Ming-Chi Tsai;Guy E. Blelloch;R. Ravi;Russell Schwartz

Year: 2011 | Volume: 8, Issue: 4 | Journal Article |

Haplotyping for Disease Association: A Combinatorial Approach

Giuseppe Lancia;R. Ravi;Romeo Rizzi

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Year: 2008 | Volume: 5, Issue: 2 | Journal Article |
Cited by: Papers (1)
We consider a combinatorial problem derived from haplotyping a population with respect to a , either recessive or dominant. Given a set of individuals, partitioned into healthy and diseased, and the corresponding sets of genotypes, we want to infer "bad" and "good" haplotypes to account for these genotypes and for the disease. Assume, for example, that the disease is recessive. Then, the resolving...Show More

Haplotyping for Disease Association: A Combinatorial Approach

Giuseppe Lancia;R. Ravi;Romeo Rizzi

Year: 2008 | Volume: 5, Issue: 2 | Journal Article |

Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference

Srinath Sridhar;Fumei Lam;Guy E. Blelloch;R. Ravi;Russell Schwartz

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Year: 2008 | Volume: 5, Issue: 3 | Journal Article |
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 inference will be required if we are to be able to continue to make effective use of the rapidly growing stores of variation data now being gathered. In this paper, we present two integer linear programm...Show More

Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference

Srinath Sridhar;Fumei Lam;Guy E. Blelloch;R. Ravi;Russell Schwartz

Year: 2008 | Volume: 5, Issue: 3 | Journal Article |

Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice

Srinath Sridhar;Kedar Dhamdhere;Guy Blelloch;Eran Halperin;R. Ravi;Russell Schwartz

IEEE/ACM Transactions on Computational Biology and Bioinformatics
Year: 2007 | Volume: 4, Issue: 4 | Journal Article |
Cited by: Papers (19)
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 the evolutionary tree, yielding an algorithm for binary character states that is computationally efficient but not robust to imperfections in real data. A near-perfect phylogeny relaxes the perfect ph...Show More

Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice

Srinath Sridhar;Kedar Dhamdhere;Guy Blelloch;Eran Halperin;R. Ravi;Russell Schwartz

Year: 2007 | Volume: 4, Issue: 4 | Journal Article |

How to pay, come what may: approximation algorithms for demand-robust covering problems

K. Dhamdhere;V. Goyal;R. Ravi;M. Singh

46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05)
Year: 2005 | Conference Paper |
Cited by: Papers (26)
Robust optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worst-case among the various uncertain scenarios in the model. While these approaches may be thought of defining data- or cost-robust problems, we formulate a new "demand-robust" model motivated by recent work on two-stage stochastic opt...Show More

How to pay, come what may: approximation algorithms for demand-robust covering problems

K. Dhamdhere;V. Goyal;R. Ravi;M. Singh

Year: 2005 | Conference Paper |

An edge in time saves nine: LP rounding approximation algorithms for stochastic network design

A. Gupta;R. Ravi;A. Sinha

45th Annual IEEE Symposium on Foundations of Computer Science
Year: 2004 | Conference Paper |
Cited by: Papers (19)
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 optimization deals with such problems where the forecasts are specified in terms of probability distributions of future data. In this paper, we broaden the set of models as well as the techniques being consid...Show More

An edge in time saves nine: LP rounding approximation algorithms for stochastic network design

A. Gupta;R. Ravi;A. Sinha

Year: 2004 | Conference Paper |

Optimal circuits for parallel multipliers

P.F. Stelling;C.U. Martel;V.G. Oklobdzija;R. Ravi

IEEE Transactions on Computers
Year: 1998 | Volume: 47, Issue: 3 | Journal Article |
Cited by: Papers (103)
We present new design and analysis techniques for the synthesis of parallel multiplier circuits that have smaller predicted delay than the best current multipliers. V.G. Oklobdzija et al. (1996) suggested a new approach, the Three-Dimensional Method (TDM), for Partial Product Reduction Tree (PPRT) design that produces multipliers that outperform the current best designs. The goal of TDM is to prod...Show More

Optimal circuits for parallel multipliers

P.F. Stelling;C.U. Martel;V.G. Oklobdzija;R. Ravi

Year: 1998 | Volume: 47, Issue: 3 | Journal Article |

A fast approximation algorithm for maximum-leaf spanning tree

Hsueh-I Lu;R. Ravi

Proceedings of the 1997 International Symposium on Parallel Architectures, Algorithms and Networks (I-SPAN'97)
Year: 1997 | Conference Paper |
Given an undirected graph G, finding a spanning tree of G with maximum number of leaves is not only NP-complete but also MAX SNP-complete. The approximation ratio of the previously best known approximation algorithm for maximum leaf spanning tree is three. However, the high-order running time required by the previous algorithm makes it impractical. In this paper we give a new factor-three approxim...Show More

A fast approximation algorithm for maximum-leaf spanning tree

Hsueh-I Lu;R. Ravi

Year: 1997 | Conference Paper |

Parallelizing elimination orders with linear fill

C. Bornstein;B. Maggs;G. Miller;R. Ravi

Proceedings 38th Annual Symposium on Foundations of Computer Science
Year: 1997 | Conference Paper |
Cited by: Papers (2)
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 and chordal graphs. For general graphs, the algorithm can be used to parallelize the order produced by some other heuristic such as minimum degree. In this case, the algorithm is applied to the chordal ...Show More

Parallelizing elimination orders with linear fill

C. Bornstein;B. Maggs;G. Miller;R. Ravi

Year: 1997 | Conference Paper |

Design strategies for optimal multiplier circuits

C. Martel;V. Oklobdzija;R. Ravi;P.F. Stelling

Proceedings of the 12th Symposium on Computer Arithmetic
Year: 1995 | Conference Paper |
We present new design and analysis techniques for the synthesis of fast parallel multiplier circuits. V.G. Oklobdzija, D. Villeger, and S.S. Lui (1995) suggested a new approach, the three dimensional method (TDM), for partial product reduction tree (PPRT) design that produces multipliers which outperform the current best designs. The goal of TDM is to produce a minimum delay PPRT using full adders...Show More

Design strategies for optimal multiplier circuits

C. Martel;V. Oklobdzija;R. Ravi;P.F. Stelling

Year: 1995 | Conference Paper |

Rapid rumor ramification: approximating the minimum broadcast time

R. Ravi

Proceedings 35th Annual Symposium on Foundations of Computer Science
Year: 1994 | Conference Paper |
Given an undirected graph representing a network of processors, and a source node containing a message that must be broadcast to all the nodes, find a scheme that accomplishes the broadcast in the minimum number of time steps. At each time step, any processor that has received the message is allowed to communicate the message to at most one of its neighbors in the network, i.e. can communicate via...Show More

Rapid rumor ramification: approximating the minimum broadcast time

R. Ravi

Year: 1994 | Conference Paper |

IEEE Account

Purchase Details

Profile Information

Need Help?

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity.
© Copyright 2025 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.