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(1-2), 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(2), 2008; 245-251.
  (with: Giuseppe Lancia, Romeo Rizzi)
  
  
• LP Rounding Approximation Algorithms for Stochastic Network Design
  Mathematics of Operations Research 32(2), 2007; 345-364.
  (with: A. Gupta, Amitabh Sinha)
  
  
• Approximation Algorithms for Problems Combining Faculty Location and Network Design
  Operations Research 54(1), 2006; 73-81.
  (with: Amitabh Sinha)
  
  
• 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(3), 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 (45730)
  (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)
  • 2006, Mini 1 (Section: A)
  • 2005, Mini 1 (Section: A)
  • 2005, Mini 1 (Section: B)

• Optimization and Decision Making (45760)
  (Masters Program)
  • 2011, Mini 1 (Section: F)
  • 2010, Mini 1 (Section: F)
  • 2010, Mini 1 (Section: M)

• Optimization for Interactive Marketing (45829)
  (Masters Program)
  • 2012, Mini 4 (Section: E)
  • 2010, Mini 4 (Section: A)
  • 2008, Mini 4 (Section: A)
  • 2007, Mini 4 (Section: A)

• Optimization for Interactive Marketing (45853)
  (Masters Program)
  • 2013, Mini 4 (Section: A)

• Mining Data for Decision Making (45863)
  (Masters Program)
  • 2006, Mini 2 (Section: A)
  • 2006, Mini 2 (Section: E)

• Business Networks (45951)
  (Masters Program)
  • 2012, Mini 2 (Section: A)
  • 2012, Mini 2 (Section: E)
  • 2012, Mini 2 (Section: M)

• Business Networks (45990)
  (Masters Program)
  • 2011, Mini 2 (Section: E)
  • 2011, Mini 2 (Section: M)
  • 2010, Mini 2 (Section: A)
  • 2010, Mini 3 (Section: A)

• Graph Theory (47835)
  (Ph.D. Program)
  • 2013, Mini 1 (Section: A)
  • 2012, Mini 1 (Section: A)
  • 2010, Mini 1 (Section: A)
  • 2008, Mini 1 (Section: A)
  • 2008, Mini 1 (Section: A)

• Networks and Matchings (47836)
  (Ph.D. Program)
  • 2010, Mini 2 (Section: A)

• Special Topics in Combinatorial Optimizatio (47853)
  (Ph.D. Program)
  • 2007, Mini 1 (Section: A)
  • 2007, Mini 1 (Section: A)

• Networks (47867)
  (Ph.D. Program)
  • 2010, Mini 4 (Section: A)

• Networks (70449)
  (BSBA Program)
  • 2010, Spring (Section: A)