home

For a reasonably updated version, please refer to my publications page in the DBLP server.

Mixed Integer Programming for Maximum-Parsimony Phylogeny Inference. Srinath Sridhar, Fumei Lam, Guy E. Blelloch, R. Ravi and Russell Schwartz, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) (2008).

The Directed Minimum Latency Problem. V. Nagarajan and R. Ravi. Proceedings of APPROX (2008).

Haplotyping for Disease Association: A Combinatorial Approach. Giuseppe Lancia, R. Ravi and Romeo Rizzi, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) (2008).

Solving the Capacitated Local Access Network Design Problem. . F. Sibel Salman, R. Ravi and John N. Hooker. INFORMS Journal on Computing (2008)

Approximating k-cuts using network strength as a Lagrangean relaxation. R. Ravi, Amitabh Sinha. European Journal of Operations Research (EJOR) (2008). An earlier version appeared in SODA 2002: 621-622.

Direct maximum parsimony phylogeny reconstruction from genotype data. S. Sridhar, F. Lam, G. E. Blelloch, R. Ravi and R. Schwartz, BMC Bioinformatics (2007).

Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice. Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi and Russell Schwartz, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB) (2007).

Pricing Tree Access Networks with Connected Backbones. V. Goyal, A. Gupta, S. Leonardi and R Ravi. Proceedings of ESA (2007).

Dial a Ride from k-forest. A. Gupta, M. Hajiyaghayi, V. Nagarajan and R. Ravi. Proceedings of ESA (2007).

Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems. V. Nagarajan and R. Ravi. Proceedings of APPROX (2007).

LP Rounding Approximation Algorithms for Stochastic Network Design A. Gupta, R. Ravi and A. Sinha. Math. Of OR, (2007). An older version titled ``An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design'' appeared in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS), (2004).

Efficiently finding the most parsimonious phylogenentic tree via linear programming S. Sridhar, F. Lam, G. E. Blelloch, R. Ravi and R. Schwartz, (Won Best Paper Award) Proceedings of ISBRA (2007).

Line-of-Sight Networks A. Frieze, J. Kleinberg, R. Ravi and W. Debany, Proceedings of SODA (2007).

An Efficient Cost-Sharing Mechanism for the Prize-Collecting Steiner Forest Problem A. Gupta, J. Konemann, S. Leonardi, R. Ravi and G. Schaefer, Proceedings of SODA (2007).

Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs R. Ravi and M. Singh, Proceedings of ICALP (2006).

Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, Srinath Sridhar, Proceedings of ICALP (2006).

Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi and Russell Schwartz, Proceedings of IWBRA (2006).

Matching Based Augmentations for Approximating Connectivity Problems R. Ravi Proceedings of LATIN (2006).

Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems. D. Golovin, V. Goyal and R. Ravi, Proceedings of STACS (2006).

How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems. K. Dhamdhere, V. Goyal, R. Ravi and M. Singh, Proceedings of FOCS (2005).

Approximation Algorithms for Requirement cut on graphs. V. Nagarajan and R. Ravi, This is a slightly corrected version of the one appearing in Proceedings of APPROX (2005).

What about Wednesday? Approximation Algorithms for Multistage Stochastic Optimization (Full Version). A. Gupta, M. Pal, R. Ravi and A. Sinha. A condensed version is to appear in Proceedings of APPROX (2005).

Finding effective support-tree preconditioners. Bruce M. Maggs, Gary L. Miller, Ojas Parekh, R. Ravi, Shan Leung Maverick Woo. SPAA 2005: 176-185 , (2005).

On Stochastic Minimum Spanning Trees. K. Dhamdhere, R. Ravi and M. Singh. Proceedings of the 11th International Conference on Integer Programming and Combinatorial Optimization (IPCO), (2005).

Approximation Algorithms for Low-Distortion Embeddings Into Low-Dimensional Spaces. M. Badoiu, K. Dhamdhere, A. Gupta, Y. Rabinovich, H. Raecke, R. Ravi and A. Sidiropoulos. Symp. on Discrete Algorithms (2005).

Primal-dual meets local search: Approximating MST's with nonuniform degree bounds. Jochen Könemann, R. Ravi. This version will appear in the SIAM J. on Computing (2005). An earlier version that appeared in STOC 2003: 389-395 is here.

Approximation algorithms for finding low-degree subgraphs. P. N. Klein, R. Krishnan, B. Raghavachari, and R. Ravi. Networks, Volume 44, Number 3, pages 203-215, (2004).

Boosted sampling: Approximation algorithms for stochastic optimization. A. Gupta, M. Pal, R. Ravi and A. Sinha. Proceedings of the 36th Annual ACM Symposium on Theory of Computing (STOC), (2004).

Multicommodity facility location. R. Ravi and A. Sinha. Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), (2004).

Hedging uncertainty: Approximation algorithms for stochastic optimization problems. R. Ravi and A. Sinha. Proceedings of the 10th International Conference on Integer Programming and Combinatorial Optimization (IPCO), (2004). A journal version appears in Math. Programming 108(1): 97-114 (2006).

A linear-time algorithm to compute a MAD tree of an interval graph. Elias Dahlhaus, Peter Dankelmann, R. Ravi. Inf. Process. Lett. 89(5): 255-259, (2004).

Approximating average distortion for embeddings into line. Kedar Dhamdhere, Anupam Gupta and R. Ravi. Proc. STACS, (2004). A more recent invited journal version to appear in the Theory of Computing Systems special issue (39(1), 2006) on STACS 2004 is here .

Min-max tree covers of graphs G. Even, N. Garg, J. Konemann, R. Ravi and A. Sinha. Operations Research Letters, 32(4):309-315, (2004). An earlier version titled "Covering graphs using trees and stars" appeared in Proceedings of the Conference on Approximation Algorithms for Combinatorial Optimization (APPROX), 2003.

On the Crossing Spanning Tree Problem. Vittorio Bilò, Vineet Goyal, R. Ravi, Mohit Singh. Proc. of APPROX-RANDOM 2004 51-64. A more recent version submitted to a journal is here.

Worst-case payoffs of a location game. Shuchi Chawla, Uday Rajan, R. Ravi, A. Sinha. Proc. of 5th ACM Conference on Electronic Commerce 2004. A more complete version is titled Min-max payoffs in a Two-player Location Game.

Profit guaranteeing mechanisms for multicast networks. Shuchi Chawla, D. Kitchin, Uday Rajan, R. Ravi, A. Sinha. Proc. of 4th ACM Conference on Electronic Commerce 2003: 190-191 (2003).

Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees. Jochen Könemann, R. Ravi. In Proc. of FSTTCS 2003: 289-301 (2003).

Approximation Algorithms for a Capacitated Network Design Problem. Refael Hassin, R. Ravi, F. Sibel Salman. Algorithmica 38(3): 417-431 (2003).

Approximation algorithms for the test cover problem.. K. M. J. de Bontridder, B. V. Halld{\'o}rsson, M. M. Halld{\'o}rsson, C. A. J. Hurkens, J. K. Lenstra, R. Ravi, and L. Stougie. Math. Program., 98(1-3, Ser. B):477--491, (2003).

Reconstructing flow paths. With Michele Conforti and Rafael Hassin, Appeared in Oper. Res. Lett. 31(3): 273-276 (2003) .

Randomized Approximation Algorithms for Query Optimization Problems on Two Processors. Eduardo Sany Laber, Ojas Parekh, R. Ravi. Proc. of ESA 2002 : 649-661 (2002).

Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems. R. Ravi, David P. Williamson. Algorithmica 34(1): 98-107 (2002). This is an erratum of a previous paper we had in Algorithmica 18(1), (1997).

Approximation algorithms for the covering Steiner problem. Goran Konjevod, R. Ravi, Aravind Srinivasan. Random Struct. Algorithms 20(3): 465-482 (2002).

A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees. Jochen Könemann, R. Ravi. SIAM J. Comput. 31(6): 1783-1793 (2002). An earlier version with a different proof of the degree approximation bound from the STOC 2000 conference is here.

On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem. With Naveen Garg, Rohit Khandekar, Goran Konjevod, F. Sibel Salman, and Amitabh Sinha IPCO 2001 170-184 (2001).

Approximation algorithms for degree-constrained minimum-cost network-design problems. With M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt. Algorithmica 31:1, 58-78 (2001).

Scheduling and Reliable Lead Time Quotation for Orders with Availability Intervals and Lead Time Sensitive Revenues. With P. Keskinocak and S. Tayur. Management Science, February 2001.

Approximating planar metrics by tree metrics . With Goran Konjevod and Fatma Sibel Salman. Information Processing Letters 80(4), 213-219 (2001).

A polylogarithmic approximation algorithm for the group Steiner problem . With Naveen Garg and Goran Konjevod. This version appeared in a special issue of Journal of Algorithms 37(1), (2000) dedicated to selected papers from SODA'98. An earlier version appears in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA '98), 253-259 (1998).

Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering problems. With Avrim Blum, Goran Konjevod and Santosh Vempala. This is a preprint of the journal version appeared in Theoretical Computer Science 235(1) (2000) (a special issue for Manuel Blum's 60th birthday). An extended abstract appeared in Proceedings of the 30th Annual Symposium on the Theory of Computing (STOC '98).

Buy-at-bulk network design: Approximating the single-sink edge installation problem . With F.S. Salman, J. Cheriyan and S. Subramanian. This version is to appear in the SIAM Journal on Optimization , 11(3), (2000). An earlier version appeared in Proc. of SODA'97, 619-628, 1997.

Approximation algorithms for capacitated network design problems. With Rafi Hassin and Fatma Sibel Salman. APPROX'00 (Workshop on Approximation Algorithms 2000).

An approximation algorithm for the covering Steiner problem. With Goran Konjevod. SODA'00 (ACM-SIAM Symposium on Discrete Algorithms 2000). A recent expanded version is now here.

GESTALT: Genomic Steiner Alignments. With Giuseppe Lancia. CPM (Combinatorial Pattern Matching) '99, 101-114 (1999).

Approximation Algorithms for the Traveling Purchaser Problem and its variants in network design . With Fatma Sibel Salman. ESA'99 (European Symposium on Algorithms 1999).

On 2-coverings and 2-packings of laminar families . With Joseph Cheriyan and Tibor Jordan. ESA'99. .

Improving minimum-cost spanning trees by upgrading nodes . With S. O. Krumke, M. V. Marathe, H. Noltemeier, S. S. Ravi, R. Sundaram, H. C. Wirth. Journal of Algorithms Vol. 33, No. 1, 92-111, 1999.

Improving spanning trees by upgrading nodes . With S. O. Krumke, H. Noltemeier, M. V. Marathe, S. S. Ravi, R. Sundaram, H. C. Wirth. Theoretical Computer Science 221 (1-2), 139-155, 1999. An earlier version appeared in Proc. 24th International Colloquium on Automata, Languages and Programming (ICALP), Bologna, Italy, LNCS Vol. 1256, pp. 281--291, Springer Verlag, July, 1997.

A polynomial-time approximation scheme for minimum routing cost spanning trees . With B. Y. Wu, G. Lancia, V. Bafna, K-M. Chao and C. Y. Tang. This version appeared in the SIAM Journal on Computing, 29(3), (1999). An earlier version appeared in Proc. of SODA'98, 21-32, 1998.

A Constant-factor Approximation Algorithm for the k-MST Problem. With Avrim Blum and Santosh Vempala. JCSS, 58:101--108 (1999). An extended abstract appears in Proceedings of the 28th Annual ACM Symposium on the Theory of Computing (STOC '96), pages 442--448.

Approximation Algorithms for Certain Network Improvement Problems . With S. O. Krumke, M. V. Marathe, H. Noltemeier and S. S. Ravi. Journal of Combinatorial Optimization Vol. 2, No. 2, 1998.

Approximation algorithms for multiple sequence alignment under a fixed evolutionary tree . With John Kececioglu. Discrete Applied Mathematics , 88, Special issue on Computational Molecular Biology, 355-366 (1998). An earlier version appeared in Proceedings of the 6th Annual Combinatorial Pattern Matching Conference (CPM '95), Springer-Verlag Lecture Notes in Computer Science 937, 330-339 (1995).

Approximating maximum-leaf spanning trees in almost linear time . With Hsueh-I Lu. Journal of Algorithms, Vol. 29, No. 1, 132-141 (1998).

Bicriteria network design problems . With M. V. Marathe, R. Sundaram, S. S. Ravi, D. J. Rosenkrantz and H. B. Hunt. Journal of Algorithms, Vol. 28, No. 1, 142-171 (1998).

A New Bound for the 2-Edge Connected Subgraph Problem . With Robert Carr. Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO '98) .

The p-neighbor k-center problem . With Shiv Chaudhuri and Naveen Garg. Information Processing Letters, 65, 131-134 (1998).

Design strategies for optimal multiplier circuits . With Chip Martel, Vojin Oklobdzija and P. F. Stelling. Proceedings of the IEEE Symposium on Computer Arithmetic, 42-49 (1995). A journal version appears as Optimal circuits for parallel multipliers in IEEE Transactions on Computers , 47, 273-286 (March 1998).

Parallel Gaussian elimination with linear fill . With Claudson Bornstein, Bruce Maggs and Gary Miller. Proceedings of IEEE Symposium on Foundations of Computer Science (FOCS '97) , 274-283 (1997).

Banishing bias from consensus sequences . With Amir Ben-Dor, Giuseppe Lancia and Jennifer Perone. Proceedings of the 8th Annual Combinatorial Pattern Matching Conference (CPM '97) , Springer-Verlag Lecture Notes in Computer Science 1264, 247-261 (1997).

Nonoverlapping local alignments (Weighted independent sets of axis-parallel rectangles) . With Vineet Bafna and Babu narayanan. Discrete Applied Mathematics , 71, Special issue on Computational Molecular Biology, 41-53 (1996). A preliminary version appeared in Proceedings of the Workshop on Algorithms and Data Structures (WADS '95), LNCS 955, 506-517 (1995).

The constrained minimum spanning tree problem . With Michel Goemans. Proc. of the Scandinavian Workshop on Algorithmic Theory (SWAT) 1996, LNCS 1097, 66-75 (1996).

Spanning trees short or small . With R. Sundaram, M. V. Marathe, S. S. Ravi and D. J. Rosenkrantz. SIAM Journal on Discrete Mathematics, 9(2)} 178-200 (1996).

A nearly best-possible approximation algorithm for node-weighted Steiner trees . With Philip Klein. Journal of Algorithms, 19, 104-115 (1995).

Computing similarity between RNA strings . With Vineet Bafna and S. Muthukrishnan. Proceedings of the 6th Annual Combinatorial Pattern Matching Conference (CPM '95) Springer-Verlag Lecture Notes in Computer Science 937, 1-16 (1995).

Of mice and men: Evolutionary distances between genomes under translocations . With John Kececioglu. Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA '95), 604-613 (1995).

When trees collide : An approximation algorithm for the generalized Steiner problem on networks. With Ajit Agrawal and Philip Klein. SIAM Journal on Computing, 24(3) 445-456 (1995). An early version appeared as Proceedings of the ACM Symposium on the Theory of Computing (STOC '91), 134-144 (1991).

An approximate max-flow min-cut relation for multicommodity flow, with applications. With Philip Klein, Satish Rao and Ajit Agrawal. Combinatorica 15(2)} 187-202 (1995).

Rapid rumor ramification: Approximating the minimum broadcast time. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS '94), 202-213 (1994).

A primal-dual approximation algorithm for the Steiner forest problem. Information Processing Letters, 50, 185-190 (1994).

Many birds with one stone: Multi-objective approximation algorithms. With M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, and H. B. Hunt. Proceedings of the ACM Symposium on the Theory of Computing (STOC '93), 438-447 (1993).

Cutting down on fill using nested dissection: provably good elimination orderings. With Ajit Agrawal and Philip Klein. Invited chapter in Graph Theory and Sparse Matrix Computation, eds. A. George, J. Gilbert, and J. W. H. Liu, Vol. 56 in the IMA Volumes in Mathematics and its Applications, Springer-Verlag (1993).

When cycles collapse: A general approximation technique for constrained two-connectivity problems. With Philip Klein. Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO '93), 39-56 (1993).

The power of local optimization: approximation algorithms for maximum-leaf spanning tree . With Hsues-I Lu. Proceedings, Thirtieth Annual Allerton Conference on Communication, Control and Computing, 533-542 (1992).

An optimal algorithm to solve the all-pair shortest path problem on interval graphs. With Madhav Marathe and C. Pandurangan. Networks, 22, 21-35 (1992).

Generalized vertex covering in interval graphs. With Madhav Marathe and C. Pandurangan. Discrete Applied Mathematics, 39, 87-93 (1992).

Ordering problems approximated: single-processor scheduling and interval graph completion. With Ajit Agrawal and Philip Klein. International Colloquium on Automata, Languages and Processing (ICALP '91), Springer-Verlag Lecture Notes in Computer Science 510, 751-762 (1991).

Approximation through multicommodity flow. With Philip Klein, Ajit Agrawal and Satish Rao. Proceedings of the IEEE Symposium on Foundations of Computer Science (FOCS '90), 726-737 (1990).