R. Ravi

View Printable Version

Carnegie Bosch Professor of Operations Research and Computer Science

Teaching and Research Interests:

• Combinatorial optimization, approximation algorithms, computational molecular biology.

Website and/or personal homepage:
http://www.gsia.cmu.edu/andrew/ravi

Published Papers: 

• Line-of-Sight Networks
  Combinatorics, Probability & Computing 18, 2009; 145-163.
  (With: A. Frieze, J. Kleinberg, W. Debany)
  
  
• Haplotyping for Disease Association: A Combinatorial Approach
  IEEE/ACM Transactions on Computational Biology and Bioinformatica 5, 2008; 245-251.
  (With: Giuseppe Lancia, Romeo Rizzi)
  
  
• LP Rounding Approximation Algorithms for Stochastic Network Design
  Mathematics of Operations Research 32, 2007; 345-364.
  (With: A. Gupta, Amitabh Sinha)
  
  
• Approximation Algorithms for Problems Combining Faculty Location and Network Design
  Operations Research 54, 2006; 73-81.
  (With: Amitabh Sinha)
  
  
• Scheduling and Reliable Lead Time Quotation for Orders with Availability Intervals and Lead Time Sensitive Revenues
  Management Science 47, February 2001; 264-279.
  (With: Pinar Keskinocak, Sridhar Tayur)
  
  
• A Polylogarithmic Approximation Algorithm for the Group Steiner Problem
  Journal of Algorithms 37, 2000; 66-84.
  (With: N. Garg, G. Konjevod)
  
  
• A Constant Factor Approximation Algorithm for the k-MST Problem
  Journal of Computer Systems & Sciences 58, 1999; 101-108.
  (With: A. Blum, S. Vempala)
  
  
• When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks
  SIAM Journal on Computing 24, 1995; 445-456.
  (With: A. Agrawal, P. Klein)
  For Further Information
  
  

Working Papers: 

• Sort-Cut: A Pareto Optimal and Semi-Truthful Mechanism for Multi-Unit Auctions with Budget-Constrained Bidders
  July, 2009.
  (With: Isa Hafalir, Sayedi Amin)
  
  
• A PTAS for Chance-Constrained Knapsack Problem with Random Item Sizes
  July, 2008.
  (With: V. Goyal)
  
  
• An FPTAS for Minizing a Class of Quasi-Concave Functions over a Convex Set
  June, 2008.
  (With: V. Goyal)
  
  
• An FPTAS for Minimizing the Product of Two Non-negative Linear Costs
  April, 2008.
  (With: V. Goyal, Latife Genc Kaya)
  
  
• Approximation Algorithms for Robust Covering Problems with Chance Constraints
  January, 2008.
  (With: V. Goyal)
  
  

Awards:

• BP Research Chair, GSIA - 1997-1998
• NSF CAREER Award - 1996-2000
• Sigma Xi Outstanding Graduate Research Prize - 1994

Editorial Boards:

• Operations Research (Associate Editor), 2006-2008
• Management Science (Associate Editor), 2004-
• ACM Transactions on Algorithms (Associate Editor), 2004-
• Networks (Associate Editor), 2003-2006
• Journal of Algorithms (Associate Editor), 2003

Courses Taught:

• Probability and Decision Making (45-730)
  (Masters Program)
  • 2008, Mini 1 (Section: A)
  • 2008, Mini 1 (Section: B)
  • 2008, Mini 1 (Section: C)
  • 2007, Mini 1 (Section: A)
  • 2007, Mini 1 (Section: B)
  
  
• Optimization for Marketing (45-829)
  (Masters Program)
  • 2007, Mini 4 (Section: A)
  
  
• Graph Theory (47-835)
  (Ph.D. Program)
  • 2008, Mini 1 (Section: A)
  
  
• Special Topics in Combinatorial Optimizatio (47-853)
  (Ph.D. Program)
  • 2007, Mini 1 (Section: A)