Ravi

PHONE

412-268-3694

OFFICE

POS - Posner Hall - Room 348C

AREA OF EXPERTISE

Operations Research

EDUCATION

Brown University - Ph D (Computer Science) - 1993
I. I. T., Madras - Bachelor of Technology (Computer Science and Engineering) - 1989

TEACHING AND RESEARCH INTERESTS

Models, methods and applications of discrete optimization.

USEFUL LINKS

Personal homepage

BIOGRAPHY

Dr. R. Ravi is the Rohet Tolani Distinguished Professor, Andris A. Zoltners Professor of Business, and Professor of Operations Research and Computer Science at Carnegie Mellon University. Ravi received his bachelor''s degree from IIT, Madras, and Master''s and doctoral degrees from Brown University, all in Computer Science. Ravi has been at the Tepper School of Business since 1995 where he served as the Associate Dean for Intellectual Strategy from 2005-2008, and Chair of the Future Educational Delivery Committee that launched the online hybrid Tepper MBA in 2013. Ravi''s main research interests are in algorithms for combinatorial optimization, and their applications in the intersection of business and technology. Ravi is interested in networks and their effects in business, a subject on which he introduced a new MBA class. He is also interested in customer-centric marketing and how to accomplish this using optimization methods on large data sets, on which he co-developed another new MBA class and co-wrote a book.   On the academic side, Ravi''s research has been continually supported by the U.S. National Science Foundation since 1995; In this period, he has supervised over a dozen doctoral students and developed over half a dozen new graduate classes. He currently serves as area editor for the INFORMS flagship journal Operations Research in charge of the discrete optimization area.

PUBLICATIONS

• Capacitated Vehicle Routing with Nonuniform Speeds

(author(s): Inge Gørtz, Marco Molinaro, Viswanath Nagarajan, R. Ravi) Mathematics of Operations Research 41(1), 2016; 318–331

• Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets

(author(s): Anupam Gupta, Viswanath Nagarajan, R. Ravi) ACM Trans. Algorithms 12(1), 2016; 10

• Customer-Centric Marketing: A Pragmatic Framework.

(author(s): R. Ravi, Baohong Sun) MIT Press, 2016

• Expertise Online Markets

(author(s): Isa Hafalir, R. Ravi, Stelios Despotakis, Amin Sayedi) Management Science

• Rumors Across Radio, Wireless, Telephone.
  Proceedings of the 35th IARCS Annual Conf. Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

(author(s): Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, Ravi Sundaram) 2015; 517-528

• Designing Overlapping Networks for Publish-Subscribe Systems
  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2015, August 24-26, 2015, Princeton, NJ, USA

(author(s): Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, Ravi Sundaram) 2015; 381–395

• Efficient cost-sharing mechanisms for prize-collecting problems

(author(s): A. Gupta, Jochen Könemann, Stefano Leonardi, R. Ravi, Guido Schäfer) Math. Program. 152(1-2), 2015; 147–188

• Improved approximations for two-stage min-cut and shortest path problems under uncertainty

(author(s): Daniel Golovin, Vineet Goyal, Valentin Polishchuk, R. Ravi, Mikko Sysikaski) Math. Program. 149(1-2), 2015; 167–194

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

(author(s): Takuro Fukunaga, Zeev Nutov, R. Ravi) SIAM J. Comput. 44(5), 2015; 1202–1229

• Minimum Makespan Multi-Vehicle Dial-a-Ride

(author(s): Inge Li Gørtz, Viswanath Nagarajan, R. Ravi) ACM Transactions on Algorithms 11(3), 2015; 23

• Recommendation Subgraphs for Web Discovery
  Proceedings of the 24th International Conference on World Wide Web, WWW 2015, Florence, Italy, May 18-22, 2015

(author(s): Arda Antikacioglu, R. Ravi, Srinath Sridhar) 2015; 77–87

• Rumors Across Radio, Wireless, Telephone
  35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2015, December 16-18, 2015, Bangalore, India

(author(s): Jennifer Iglesias, Rajmohan Rajaraman, R. Ravi, Ravi Sundaram) 2015; 517–528

• Running Errands in Time: Approximation Algorithms for Stochastic Orienteering

(author(s): Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi) Math. Oper. Res. 40(1), 2015; 56–79

• A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs
  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain

(author(s): Jeremy Karp, R. Ravi) 2014; 284–296

• Algorithm Theory - SWAT 2014 - 14th Scandinavian Symposium and Workshops, Copenhagen, Denmark, July 2-4, 2014. Proceedings

Springer 8503, 2014

• Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem
  Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain

(author(s): Takuro Fukunaga, Afshin Nikzad, R. Ravi) 2014; 209–225

• Graph-TSP from Steiner Cycles
  Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers

(author(s): Satoru Iwata, Alantha Newman, R. Ravi) 2014; 312–323

• New approaches to multi-objective optimization

(author(s): Fabrizio Grandoni, R. Ravi, Mohit Singh, Rico Zenklusen) Math. Program. 146(1-2), 2014; 525–554

• Sending Secrets Swiftly: Approximation Algorithms for Generalized Multicast Problems
  Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part II

(author(s): Afshin Nikzad, R. Ravi) 2014; 568–607

• Short Tours through Large Linear Forests
  Integer Programming and Combinatorial Optimization - 17th International Conference, IPCO 2014, Bonn, Germany, June 23-25, 2014. Proceedings

(author(s): Uriel Feige, R. Ravi, Mohit Singh) 2014; 273–284

• The Geometry of Online Packing Linear Programs

(author(s): Marco Molinaro, R. Ravi) Math. Oper. Res. 39(1), 2014; 46–59

• Thresholded covering algorithms for robust and max-min optimization

(author(s): Anupam Gupta, Viswanath Nagarajan, R. Ravi) Math. Program. 146(1-2), 2014; 583–615

• Efficient Cost-Sharing Mechanisms for Prize-Collecting Problems

(author(s): Anupam Gupta, Jochen Konemann, Stefano Leonardi, R. Ravi, Guido Schaefer) Mathematical Programming Series A, 2014; 1-42

• Complexity of Transmission Network Expansion Planning

(author(s): David Oertel, R. Ravi) Energy Systems 5(1), 2014; 179-207

• An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set

(author(s): Vineet Goyal, R. Ravi) Operations Research Letters 41(2), 2013; 191-196

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

(author(s): Ming-Chi Tsai, Guy Blelloch, R. Ravi, Russell Schwartz) IEEE/ACM Transactions on Computational Biology Bioinformatics 10(5), 2013; 1137-1149

• Approximating max-min weighted T-joins

(author(s): Satoru Iwata, R. Ravi) Operations Research Letters 41(4), 2013; 321-324

• Approximation algorithms for distance constrained vehicle routing problems

(author(s): Viswanath Nagarajan, R. Ravi) Networks 59(2), 2012; 209-214

• Approximation Algorithms for VRP with Stochastic Demands

(author(s): Anupam Gupta, Viswanath Nagarajan, R. Ravi) Operations Research 60(1), 2012; 123-127

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

(author(s): Takuro Fukunaga, R. Ravi) Proceedings of the IEEE Conference on the Foundations of Computer Science 2012, 2012; 263-272

• Online and Stochastic Survivable Network Design

(author(s): Anupam Gupta, Ravishankar Krishnaswamy, Viswanath Nagarajan, R. Ravi) SIAM Journal on Computing 41(6), 2012; 1649-1672

• A Near Pareto Optimal Auction with Budget Constraints

(author(s): Isa Hafalir, R. Ravi, Amin Sayedi) Games and Economic Behavior 74, 2012; 699-708

• Sampling And Cost-Sharing: Approximation Algorithms For Stochastic Optimization Problems

(author(s): Anupam Gupta, Martin Pal, R. Ravi, Amitabh Sinha) Siam Journal On Computing 40(5), 2011; 1361-1401

• An Optimization-Based Sampling Scheme For Phylogenetic Trees

(author(s): Navodit Misra, Guy Blelloch, R. Ravi, Russell Schwartz) Journal Of Computational Biology 18(11), 2011; 1599-1609

• Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits

(author(s): Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi) Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2011

• The Directed Orienteering Problem

(author(s): Viswanath Nagarajan, R. Ravi) Algorithmica 60(4), 2011; 1017-1030

• A Consensus Tree Approach For Reconstructing Human Evolutionary History And Detecting Population Substructure

(author(s): Ming-Chi Tsai, Guy Blelloch, R. Ravi, Russell Schwartz) Ieee-Acm Transactions On Computational Biology And Bioinformatics 8(4), 2011; 918-928

• Iterative Methods in Combinatorial Optimization

(author(s): Lap Chi Lau, R. Ravi, Mohit Singh) Cambridge University Press, 2011

• We Know Who You Followed Last Summer: Inferring Social Link Creation Times in Twitter

Proc. of 20th International Conference on World Wide Web (WWW), 2011

• Generalized Buneman Pruning For Inferring The Most Parsimonious Multi-State Phylogeny

(author(s): Navodit Misra, Guy Blelloch, R. Ravi, Russell Schwartz) Journal Of Computational Biology 18(3), 2011; 445-457

• An Fptas For Minimizing The Product Of Two Non-Negative Linear Cost Functions

(author(s): Vineet Goyal, Latife Genc-Kaya, R. Ravi) Mathematical Programming 126(2), 2011; 401-405

• Approximation Algorithms For Multicommodity Facility Location Problems

(author(s): R. Ravi, Amitabh Sinha) Siam Journal On Discrete Mathematics 24(2), 2010; 538-551

• Integrated Optimization Of Customer And Supplier Logistics At Robert Bosch Llc

(author(s): Hakan Yildiz, R. Ravi, Wayne Fairey) European Journal Of Operational Research 207(1), 2010; 456-464

• An Improved Approximation Algorithm For Requirement Cut

(author(s): Anupam Gupta, Viswanath Nagarajan, R. Ravi) Operations Research Letters 38(4), 2010; 322-325

• A Ptas For The Chance-Constrained Knapsack Problem With Random Item Sizes

(author(s): Vineet Goyal, R. Ravi) Operations Research Letters 38(3), 2010; 161-164

• Approximation Algorithms For Requirement Cut On Graphs

(author(s): Viswanath Nagarajan, R. Ravi) Algorithmica 56(2), 2010; 198-213

• Line-Of-Sight Networks

(author(s): Alan Frieze, Jon Kleinberg, R. Ravi, Warren Debany) Combinatorics Probability & Computing 18(2-Jan), 2009; 145-163

• Haplotyping For Disease Association: A Combinatorial Approach

(author(s): Giuseppe Lancia, R. Ravi, Romeo Rizzi) Ieee-Acm Transactions On Computational Biology And Bioinformatics 5(2), 2008; 245-251

• Solving The Capacitated Local Access Network Design Problem

(author(s): F. Sibel Salman, R. Ravi, John Hooker) Informs Journal On Computing 20(2), 2008; 243-254

• Approximating K-Cuts Using Network Strength As A Lagrangean Relaxation

(author(s): R. Ravi, Arnitabh Sinha) European Journal Of Operational Research 186(1), 2008; 77-90

• Lp Rounding Approximation Algorithms For Stochastic Network Design

(author(s): Anupam Gupta, R. Ravi, Amitabh Sinha) Mathematics Of Operations Research 32(2), 2007; 345-364

• Matching Based Augmentations For Approximating Connectivity Problems

Latin 2006: Theoretical Informatics 3887, 2006; 13-24

• Pay Today For A Rainy Day: Improved Approximation Algorithms For Demand-Robust Min-Cut And Shortest Path Problems

(author(s): D Golovin, Vineet Goyal, R. Ravi) Stacs 2006, Proceedings 3884, 2006; 206-217

• Min-Max Payoffs In A Two-Player Location Game

(author(s): S Chawla, Uday Rajan, R. Ravi, A Sinha) Operations Research Letters 34(5), 2006; 499-507

• Hedging Uncertainty: Approximation Algorithms For Stochastic Optimization Problems

(author(s): R. Ravi, A Sinha) Mathematical Programming 108(1), 2006; 97-114

• Approximation Algorithms For Minimizing Average Distortion

(author(s): K Dhamdhere, A Gupta, R. Ravi) Theory Of Computing Systems 39(1), 2006; 93-111

• Approximation Algorithms For Problems Combining Facility Location And Network Design

(author(s): R. Ravi, A Sinha) Operations Research 54(1), 2006; 73-81

• Approximation Algorithms For Requirement Cut On Graphs

(author(s): V Nagarajan, R. Ravi) Approximation, Randomization And Combinatorial Optimization: Algorithms And Techniques 3624, 2005; 209-220

• On Two-Stage Stochastic Minimum Spanning Trees

(author(s): K Dhamdhere, R. Ravi, M Singh) Integer Programming And Combinatorial Optimization, Proceedings 3509, 2005; 321-334

• Primal-Dual Meets Local Search: Approximating Msts With Nonuniform Degree Bounds

(author(s): J Konemann, R. Ravi) Siam Journal On Computing 34(3), 2005; 763-773

• What About Wednesday? Approximation Algorithms For Multistage Stochastic Optimization

(author(s): A Gupta, M Pal, R. Ravi, A Sinha) Approximation, Randomization And Combinatorial Optimization: Algorithms And Techniques 3624, 2005; 86-98

• On The Crossing Spanning Tree Problem

(author(s): V Bilo, Vineet Goyal, R. Ravi, M Singh) Approximation, Randomization, And Combinatorial Optimization: Algorithms And Techniques, Proceedings 3122, 2004; 51-60

• Min-Max Tree Covers Of Graphs

(author(s): G Even, N Garg, J Konemann, R. Ravi, A Sinha) Operations Research Letters 32(4), 2004; 309-315

• A Linear-Time Algorithm To Compute A Mad Tree Of An Interval Graph

(author(s): E Dahlhaus, P Dankelmann, R. Ravi) Information Processing Letters 89(5), 2004; 255-259

• Approximation Algorithms For A Capacitated Network Design Problem

(author(s): R Hassin, R. Ravi, FS Salman) Algorithmica 38(3), 2004; 417-431

• Approximation Algorithms For The Test Cover Problem

(author(s): KMJ De Bontridder, BV Halldorsson, MM Halldorsson, CAJ Hurkens, JK Lenstra, R. Ravi, L Stougie) Mathematical Programming 98(3-Jan), 2003; 477-491

• Reconstructing Edge-Disjoint Paths

(author(s): M Conforti, R Hassin, R. Ravi) Operations Research Letters 31(4), 2003; 273-276

• Bicriteria Spanning Tree Problems

Approximation Algorithms For Combinatorial Optimization, Proceedings 2462, 2002; 4-Mar

• A Matter Of Degree: Improved Approximation Algorithms For Degree-Bounded Minimum Spanning Trees

(author(s): J Konemann, R. Ravi) Siam Journal On Computing 31(6), 2002; 1783-1793

• An Approximation Algorithm For Minimum-Cost Vertex-Connectivity Problems (Vol 18, Pg 21, 1997)

(author(s): R. Ravi, DP Williamson) Algorithmica 34(1), 2002; 98-107

• Approximation Algorithms For The Covering Steiner Problem

(author(s): G Konjevod, R. Ravi, A Srinivasan) Random Structures & Algorithms 20(3), 2002; 465-482

• On Approximating Planar Metrics By Tree Metrics

(author(s): G Konjevod, R. Ravi, FS Salman) Information Processing Letters 80(4), 2001; 213-219

• Approximation Algorithms For Degree-Constrained Minimum-Cost Network-Design Problems

(author(s): R. Ravi, MV Marathe, SS Ravi, DJ Rosenkrantz, HB Hunt) Algorithmica 31(1), 2001; 58-78

• Approximating The Single-Sink Link-Installation Problem In Network Design

(author(s): FS Salman, J Cheriyan, R. Ravi, S Subramanian) Siam Journal On Optimization 11(3), 2001; 595-610

• Scheduling And Reliable Lead-Time Quotation For Orders With Availability Intervals And Lead-Time Sensitive Revenues

(author(s): P Keskinocak, R. Ravi, Sridhar Tayur) Management Science 47(2), 2001; 264-279

• A Polylogarithmic Approximation Algorithm For The Group Steiner Tree Problem

(author(s): N Garg, G Konjevod, R. Ravi) Journal Of Algorithms 37(1), 2000; 66-84

• Approximation Algorithms For The Multiple Knapsack Problem With Assignment Restrictions

(author(s): M Dawande, J Kalagnanam, P Keskinocak, FS Salman, R. Ravi) Journal Of Combinatorial Optimization 4(2), 2000; 171-186

• Semi-Definite Relaxations For Minimum Bandwidth And Other Vertex-Ordering Problems

(author(s): A Blum, G Konjevod, R. Ravi, S Vempala) Theoretical Computer Science 235(1), 2000; 25-42

• A Polynomial-Time Approximation Scheme For Minimum Routing Cost Spanning Trees

(author(s): BY Wu, G Lancia, V Bafna, KM Chao, R. Ravi, CAY Tang) Siam Journal On Computing 29(3), 2000; 761-778

• Approximation Algorithms For The Traveling Purchaser Problem And Its Variants In Network Design

(author(s): R. Ravi, FS Salman) Algorithms - Esa''99 1643, 1999; 29-40

• On 2-Coverings And 2-Packings Of Laminar Families

(author(s): J Cheriyan, T Jordan, R. Ravi) Algorithms - Esa''99 1643, 1999; 510-520

• Improving Minimum Cost Spanning Trees By Upgrading Nodes

(author(s): SO Krumke, MV Marathe, H Noltemeier, R. Ravi, SS Ravi, R Sundarum, HC Wirth) Journal Of Algorithms 33(1), 1999; 92-111

• Improving Spanning Trees By Upgrading Nodes

(author(s): SO Krumke, H Noltemeier, HC Wirth, MV Marathe, R. Ravi, SS Ravi, R Sundaram) Theoretical Computer Science 221(2-Jan), 1999; 139-155

• A Constant-Factor Approximation Algorithm For The K-Mst Problem

(author(s): A Blum, R. Ravi, S Vempala) Journal Of Computer And System Sciences 58(1), 1999; 101-108

• A New Bound For The 2-Edge Connected Subgraph Problem

(author(s): R Carr, R. Ravi) Integer Programming And Combinatorial Optimization 1412, 1998; 112-125

• Approximation Algorithms For Certain Network Improvement Problems

(author(s): SO Krumke, MV Marathe, H Noltemeier, R. Ravi, SS Ravi) Journal Of Combinatorial Optimization 2(3), 1998; 257-288

• Approximation Algorithms For Multiple Sequence Alignment Under A Fixed Evolutionary Tree

(author(s): R. Ravi, JD Kececioglu) Discrete Applied Mathematics 88(3-Jan), 1998; 355-366

• Approximating Maximum Leaf Spanning Trees In Almost Linear Time

(author(s): HI Lu, R. Ravi) Journal Of Algorithms 29(1), 1998; 132-141

• Bicriteria Network Design Problems

(author(s): MV Marathe, R. Ravi, R Sundaram, SS Ravi, DJ Rosenkrantz, HB Hunt) Journal Of Algorithms 28(1), 1998; 142-171

• Optimal Circuits For Parallel Multipliers

(author(s): PF Stelling, CU Martel, VG Oklobdzija, R. Ravi) Ieee Transactions On Computers 47(3), 1998; 273-285

• The P-Neighbor K-Center Problem

(author(s): S Chaudhuri, N Garg, R. Ravi) Information Processing Letters 65(3), 1998; 131-134

• An Approximation Algorithm For Minimum-Cost Vertex-Connectivity Problems

(author(s): R. Ravi, DP Williamson) Algorithmica 18(1), 1997; 21-43

• Nonoverlapping Local Alignments (Weighted Independent Sets Of Axis-Parallel Rectangles)

(author(s): V Bafna, B Narayanan, R. Ravi) Discrete Applied Mathematics 71(3-Jan), 1996; 41-53

AWARDS AND HONORS

• Tepper School of Business - George Leland Bach Award for Excellence in the MBA Classroom (2013)
• Carnegie Bosch Institute - Carnegie Bosch Chair (2006)
• NSF - CAREER Award (2006)

UNIVERSITY SERVICE

• Future Educational Delivery Committee, Committee Chair, Convened and led the ten-person faculty committee that designed and launched the online hybrid Tepper MBA in the Fall of 2013, and transitioned to leading the OH Faculty advisory committee of four faculty members. (2012 - 2013)
• Associate Dean for Intellectual Strategy, Tepper School of Business, Precursor of the two current positions of the senior associate deans for research and education in the school (2005 - 2008)

PROFESSIONAL ACTIVITIES

• Senior Editor, Operations Research, Area Editor for Discrete Optimization (January 2012 -)
• Committee Member, Association for Computing Machinery (ACM), Program Committee for the 2016 Annual Symposium on the Theory of Computing (STOC) (November 2015 - March 2016)
• Associate Editor, ACM Transactions on Algorithms (January 2004 - January 2015)
• Committee Chair, 14th Scandinavian Symposium and Workshops on Algorithm Theory (July 2014 - July 2014)
• Associate Editor, Management Science (January 2004 - December 2012)
• Committee Chair, IEEE, Symposium on Foundations of Computer Science (FOCS) (October 2008 - October 2008)
• Associate Editor, Networks (January 2003 - 2006)
• Associate Editor, Journal of Algorithms (January 2003 - December 2003)

COURSES TAUGHT

• Graph Theory (47835) 2016 Mini 1 Section: A

• Business Networks (45951) 2016 Mini 2 Section: A, E
  2015 Mini 1 Section: M

• Optimization for Interactive Marketing (45853) 2016 Mini 2 Section: A
  2016 Mini 4 Section: A

• Special Topics in Combinatorial Optimization (47853) 2016 Mini 4 Section: A

• Probability And Statistics (45750) 2015 Mini 1 Section: F, M

• Networks and Matchings (47836) 2010 Mini 2 Section: A

• Networks (70449) 2010 Section: A

• Networks (47867) 2010 Mini 4 Section: A

• Special Topics in Combinatorial Optimizatio (47853) 2007 Mini 1 Section: A

• Optimization for Interactive Marketing (45829) 2007 Mini 4 Section: A

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

• Approximation Algorithms II (47850) 2006 Section: A

• Approximation Algorithms I (47849) 2005 Section: A