R. Ravi

Orcid: 0000-0001-7603-1207

Affiliations:
  • Carnegie Mellon University, Pittsburgh, PA, USA


According to our database1, R. Ravi authored at least 217 papers between 1990 and 2024.

Collaborative distances:

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
HITSnDIFFs: From Truth Discovery to Ability Discovery by Recovering Matrices with the Consecutive Ones Property.
CoRR, 2024

2023
Vertex downgrading to minimize connectivity.
Math. Program., May, 2023

Order Fulfillment Under Pick Failure in Omnichannel Ship-From-Store Programs.
Manuf. Serv. Oper. Manag., March, 2023

A new integer programming formulation of the graphical traveling salesman problem.
Math. Program., February, 2023

Short-lived High-volume Multi-A(rmed)/B(andits) Testing.
CoRR, 2023

Markdown Pricing Under an Unknown Parametric Demand Model.
CoRR, 2023

Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Approximation Algorithms for Steiner Tree Augmentation Problems.
Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Short-lived High-volume Bandits.
Proceedings of the International Conference on Machine Learning, 2023

2022
On small-depth tree augmentations.
Oper. Res. Lett., 2022

Coloring down: 3/2-approximation for special cases of the weighted tree augmentation problem.
Oper. Res. Lett., 2022

Approximation algorithm for the 2-stage stochastic matroid base problem.
Oper. Res. Lett., 2022

Effective Online Order Acceptance Policies for Omnichannel Fulfillment.
Manuf. Serv. Oper. Manag., 2022

Two-level hub Steiner trees.
Inf. Process. Lett., 2022

Combinatorial Heuristics for Inventory Routing Problems.
INFORMS J. Comput., 2022

New and improved approximation algorithms for Steiner Tree Augmentation Problems.
CoRR, 2022

Unit Perturbations in Budgeted Spanning Tree Problems.
CoRR, 2022

Approximation Algorithms for Replenishment Problems with Fixed Turnover Times.
Algorithmica, 2022

Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions (Extended Abstract).
Proceedings of the Fifteenth International Symposium on Combinatorial Search, 2022

Dynamic Pricing with Monotonicity Constraint under Unknown Parametric Demand Model.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Allocation Schemes in Analytic Evaluation: Applicant-Centric Holistic or Attribute-Centric Segmented?
Proceedings of the Tenth AAAI Conference on Human Computation and Crowdsourcing, 2022

2021
A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs.
Oper. Res. Lett., 2021

Local improvement algorithms for a path packing problem: A performance analysis based on linear programming.
Oper. Res. Lett., 2021

Shorter tours and longer detours: uniform covers and a bit beyond.
Math. Program., 2021

The Beneficial Effects of Ad Blockers.
Manag. Sci., 2021

An optimal rounding for half-integral weighted minimum strongly connected spanning subgraph.
Inf. Process. Lett., 2021

Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models.
CoRR, 2021

A heuristic for statistical seriation.
Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence, 2021

Learnable and Instance-Robust Predictions for Online Matching, Flows and Load Balancing.
Proceedings of the 29th Annual European Symposium on Algorithms, 2021

Using Predicted Weights for Ad Delivery.
Proceedings of the 2021 SIAM Conference on Applied and Computational Discrete Algorithms, 2021

2020
The Approximability of Multiple Facility Location on Directed Networks with Random Arc Failures.
Algorithmica, 2020

Primal-Dual 2-Approximation Algorithm for the Monotonic Multiple Depot Heterogeneous Traveling Salesman Problem.
Proceedings of the 17th Scandinavian Symposium and Workshops on Algorithm Theory, 2020

Stretching the Effectiveness of MLE from Accuracy to Bias for Pairwise Comparisons.
Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, 2020

2019
Algorithms for automatic ranking of participants and tasks in an anonymized contest.
Theor. Comput. Sci., 2019

A New System-Wide Diversity Measure for Recommendations with Efficient Algorithms.
SIAM J. Math. Data Sci., 2019

Approximation Algorithms for Low-Distortion Embeddings into Low-Dimensional Spaces.
SIAM J. Discret. Math., 2019

Downgrading to Minimize Connectivity.
CoRR, 2019

Inventory Routing Problem with Facility Location.
Proceedings of the Algorithms and Data Structures - 16th International Symposium, 2019

Optimal Decision Tree with Noisy Outcomes.
Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Multicommodity Multicast, Wireless and Fast.
Proceedings of the 27th Annual European Symposium on Algorithms, 2019

Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty.
Proceedings of the Approximation, 2019

2018
Plane Gossip: Approximating Rumor Spread in Planar Graphs.
Proceedings of the LATIN 2018: Theoretical Informatics, 2018

2017
Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems.
Math. Oper. Res., 2017

Expertise in Online Markets.
Manag. Sci., 2017

Multiple facility location on a network with linear reliability order of edges.
J. Comb. Optim., 2017

Cover and Conquer: Augmenting Decompositions for Connectivity Problems.
CoRR, 2017

Network Flow Based Post Processing for Sales Diversity.
CoRR, 2017

LAST but not Least: Online Spanners for Buy-at-Bulk.
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 2017

Post Processing Recommender Systems for Diversity.
Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Halifax, NS, Canada, August 13, 2017

Single-Sink Fractionally Subadditive Network Design.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

Randomized Contractions for Multiobjective Minimum Cuts.
Proceedings of the 25th Annual European Symposium on Algorithms, 2017

On the Integrality Gap of the Prize-Collecting Steiner Forest LP.
Proceedings of the Approximation, 2017

2016
Hardware Implementation of Architecture Techniques for Fast Efficient Lossless Image Compression System.
Wirel. Pers. Commun., 2016

Robust and MaxMin Optimization under Matroid and Knapsack Uncertainty Sets.
ACM Trans. Algorithms, 2016

Current Trends in Combinatorial Optimization (NII Shonan Meeting 2016-7).
NII Shonan Meet. Rep., 2016

Capacitated Vehicle Routing with Nonuniform Speeds.
Math. Oper. Res., 2016

A -approximation algorithm for Graphic TSP in cubic bipartite graphs.
Discret. Appl. Math., 2016

Balls and Funnels: Energy Efficient Group-to-Group Anycasts.
Proceedings of the Computing and Combinatorics - 22nd International Conference, 2016

2015
The Performances Analysis of Fast Efficient Lossless Satellite Image Compression and Decompression for Wavelet Based Algorithm.
Wirel. Pers. Commun., 2015

Minimum Makespan Multi-Vehicle Dial-a-Ride.
ACM Trans. Algorithms, 2015

Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design.
SIAM J. Comput., 2015

Efficient cost-sharing mechanisms for prize-collecting problems.
Math. Program., 2015

Improved approximations for two-stage min-cut and shortest path problems under uncertainty.
Math. Program., 2015

Running Errands in Time: Approximation Algorithms for Stochastic Orienteering.
Math. Oper. Res., 2015

Recommendation Subgraphs for Web Discovery.
Proceedings of the 24th International Conference on World Wide Web, 2015

Rumors Across Radio, Wireless, Telephone.
Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science, 2015

Designing Overlapping Networks for Publish-Subscribe Systems.
Proceedings of the Approximation, 2015

2014
Thresholded covering algorithms for robust and max-min optimization.
Math. Program., 2014

New approaches to multi-objective optimization.
Math. Program., 2014

The Geometry of Online Packing Linear Programs.
Math. Oper. Res., 2014

Graph-TSP from Steiner Cycles.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2014

Short Tours through Large Linear Forests.
Proceedings of the Integer Programming and Combinatorial Optimization, 2014

Sending Secrets Swiftly: Approximation Algorithms for Generalized Multicast Problems.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

A 9/7 -Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs.
Proceedings of the Approximation, 2014

Deliver or hold: Approximation Algorithms for the Periodic Inventory Routing Problem.
Proceedings of the Approximation, 2014

2013
Coalescent-Based Method for Learning Parameters of Admixture Events from Large-Scale Genetic Variation Data.
IEEE ACM Trans. Comput. Biol. Bioinform., 2013

Approximating max-min weighted T-joins.
Oper. Res. Lett., 2013

An FPTAS for minimizing a class of low-rank quasi-concave functions over a convex set.
Oper. Res. Lett., 2013

2012
Online and Stochastic Survivable Network Design.
SIAM J. Comput., 2012

Approximation algorithms for distance constrained vehicle routing problems.
Networks, 2012

Technical Note - Approximation Algorithms for VRP with Stochastic Demands.
Oper. Res., 2012

A near Pareto optimal auction with budget constraints.
Games Econ. Behav., 2012

Iterative Methods in Combinatorial Optimization (Invited Talk).
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

Approximation algorithms for stochastic orienteering.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

Iterative Rounding Approximation Algorithms for Degree-Bounded Node-Connectivity Network Design.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

2011
A Consensus Tree Approach for Reconstructing Human Evolutionary History and Detecting Population Substructure.
IEEE ACM Trans. Comput. Biol. Bioinform., 2011

Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems.
SIAM J. Comput., 2011

Special Section on Foundations of Computer Science.
SIAM J. Comput., 2011

An FPTAS for minimizing the product of two non-negative linear cost functions.
Math. Program., 2011

An Optimization-Based Sampling Scheme for Phylogenetic Trees.
J. Comput. Biol., 2011

Generalized Buneman Pruning for Inferring the Most Parsimonious Multi-State Phylogeny.
J. Comput. Biol., 2011

The Query-commit Problem
CoRR, 2011

The Directed Orienteering Problem.
Algorithmica, 2011

We know who you followed last summer: inferring social link creation times in twitter.
Proceedings of the 20th International Conference on World Wide Web, 2011

Capacitated Vehicle Routing with Non-uniform Speeds.
Proceedings of the Integer Programming and Combinatoral Optimization, 2011

Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits.
Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010
Dial a Ride from <i>k</i>-forest.
ACM Trans. Algorithms, 2010

Approximation Algorithms for Multicommodity Facility Location Problems.
SIAM J. Discret. Math., 2010

Simpler analysis of LP extreme points for traveling salesman and survivable network design problems.
Oper. Res. Lett., 2010

An improved approximation algorithm for requirement cut.
Oper. Res. Lett., 2010

A PTAS for the chance-constrained knapsack problem with random item sizes.
Oper. Res. Lett., 2010

Integrated optimization of customer and supplier logistics at Robert Bosch LLC.
Eur. J. Oper. Res., 2010

Approximation Algorithms for Optimal Decision Trees and Adaptive TSP Problems
CoRR, 2010

Approximation Algorithms for Requirement Cut on Graphs.
Algorithmica, 2010

Game-Theoretic Models of Information Overload in Social Networks.
Proceedings of the Algorithms and Models for the Web-Graph - 7th International Workshop, 2010

Tree Embeddings for Two-Edge-Connected Network Design.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009
Line-of-Sight Networks.
Comb. Probab. Comput., 2009

Sort-Cut: A Pareto Optimal and Semi-Truthful Mechanism for Multi-Unit Auctions with Budget-Constrained Bidders
CoRR, 2009

Iterative Methods in Combinatorial Optimization.
Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

Tractable Cases of Facility Location on a Network with a Linear Reliability Order of Links.
Proceedings of the Algorithms, 2009

Iterative Rounding for Multi-Objective Optimization Problems.
Proceedings of the Algorithms, 2009

2008
Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference.
IEEE ACM Trans. Comput. Biol. Bioinform., 2008

Haplotyping for Disease Association: A Combinatorial Approach.
IEEE ACM Trans. Comput. Biol. Bioinform., 2008

Solving the Capacitated Local Access Network Design Problem.
INFORMS J. Comput., 2008

Approximating k.
Eur. J. Oper. Res., 2008

The Directed Minimum Latency Problem.
Proceedings of the Approximation, 2008

2007
Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice.
IEEE ACM Trans. Comput. Biol. Bioinform., 2007

LP Rounding Approximation Algorithms for Stochastic Network Design.
Math. Oper. Res., 2007

Dial a Ride from k-forest
CoRR, 2007

Direct maximum parsimony phylogeny reconstruction from genotype data.
BMC Bioinform., 2007

An efficient cost-sharing mechanism for the prize-collecting Steiner forest problem.
Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Efficiently Finding the Most Parsimonious Phylogenetic Tree Via Linear Programming.
Proceedings of the Bioinformatics Research and Applications, Third International Symposium, 2007

Pricing Tree Access Networks with Connected Backbones.
Proceedings of the Algorithms, 2007

Poly-logarithmic Approximation Algorithms for Directed Vehicle Routing Problems.
Proceedings of the Approximation, 2007

2006
Min-Max payoffs in a two-player location game.
Oper. Res. Lett., 2006

Approximation Algorithms for Minimizing Average Distortion.
Theory Comput. Syst., 2006

Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems.
Math. Program., 2006

Approximation Algorithms for Problems Combining Facility Location and Network Design.
Oper. Res., 2006

Bayesian Optimal No-Deficit Mechanism Design.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems.
Proceedings of the STACS 2006, 2006

Matching Based Augmentations for Approximating Connectivity Problems.
Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees.
Proceedings of the Computational Science, 2006

Delegate and Conquer: An LP-Based Approximation Algorithm for Minimum Degree MSTs.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Fixed Parameter Tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Minimum Vehicle Routing with a Common Deadline.
Proceedings of the Approximation, 2006

2005
Primal-Dual Meets Local Search: Approximating MSTs With Nonuniform Degree Bounds.
SIAM J. Comput., 2005

Finding effective support-tree preconditioners.
Proceedings of the SPAA 2005: Proceedings of the 17th Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2005

Approximation algorithms for low-distortion embeddings into low-dimensional spaces.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

On Two-Stage Stochastic Minimum Spanning Trees.
Proceedings of the Integer Programming and Combinatorial Optimization, 2005

How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

What About Wednesday? Approximation Algorithms for Multistage Stochastic Optimization.
Proceedings of the Approximation, 2005

2004
Min-max tree covers of graphs.
Oper. Res. Lett., 2004

Approximation algorithms for finding low-degree subgraphs.
Networks, 2004

A linear-time algorithm to compute a MAD tree of an interval graph.
Inf. Process. Lett., 2004

Approximation Algorithms for a Capacitated Network Design Problem.
Algorithmica, 2004

Boosted sampling: approximation algorithms for stochastic optimization.
Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Multicommodity facility location.
Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

Worst-case payoffs of a location game.
Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 2004

An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

On the Crossing Spanning Tree Problem.
Proceedings of the Approximation, 2004

2003
Reconstructing edge-disjoint paths.
Oper. Res. Lett., 2003

Approximation algorithms for the test cover problem.
Math. Program., 2003

Primal-dual meets local search: approximating MST's with nonuniform degree bounds.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Profit guaranteeing mechanisms for multicast networks.
Proceedings of the Proceedings 4th ACM Conference on Electronic Commerce (EC-2003), 2003

Covering Graphs Using Trees and Stars.
Proceedings of the Approximation, 2003

Quasi-polynomial Time Approximation Algorithm for Low-Degree Minimum-Cost Steiner Trees.
Proceedings of the FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science, 2003

2002
A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees.
SIAM J. Comput., 2002

Approximation algorithms for the covering Steiner problem.
Random Struct. Algorithms, 2002

Erratum: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems.
Algorithmica, 2002

Approximating k-cuts via network strength.
Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002

Randomized Approximation Algorithms for Query Optimization Problems on Two Processors.
Proceedings of the Algorithms, 2002

Bicriteria Spanning Tree Problems.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2002

2001
Approximating the Single-Sink Link-Installation Problem in Network Design.
SIAM J. Optim., 2001

Scheduling and Reliable Lead-Time Quotation for Orders with Availability Intervals and Lead-Time Sensitive Revenues.
Manag. Sci., 2001

On approximating planar metrics by tree metrics.
Inf. Process. Lett., 2001

Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems.
Algorithmica, 2001

On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 2001

On the Approximability of the Minimum Test Collection Problem.
Proceedings of the Algorithms, 2001

2000
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems.
Theor. Comput. Sci., 2000

Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions.
J. Comb. Optim., 2000

A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem.
J. Algorithms, 2000

An approximation algorithm for the covering Steiner problem.
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

1999
Improving Spanning Trees by Upgrading Nodes.
Theor. Comput. Sci., 1999

A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees.
SIAM J. Comput., 1999

A Constant-Factor Approximation Algorithm for the <i>k</i>-MST Problem.
J. Comput. Syst. Sci., 1999

Improving Minimum Cost Spanning Trees by Upgrading Nodes.
J. Algorithms, 1999

Redeeming Nested Dissection: Parallelism Implies Fill.
Proceedings of the Ninth SIAM Conference on Parallel Processing for Scientific Computing, 1999

Approximation Algorithms for the Traveling Purchaser Problem and its Variants in Network Design.
Proceedings of the Algorithms, 1999

On 2-Coverings and 2-Packings of Laminar Families.
Proceedings of the Algorithms, 1999

GESTALT: Genomic Steiner Alignments.
Proceedings of the Combinatorial Pattern Matching, 10th Annual Symposium, 1999

1998
Optimal Circuits for Parallel Multipliers.
IEEE Trans. Computers, 1998

Approximation Algorithms for Certain Network Improvement Problems.
J. Comb. Optim., 1998

Bicriteria Network Design Problems.
J. Algorithms, 1998

Approximating Maximum Leaf Spanning Trees in Almost Linear Time.
J. Algorithms, 1998

The <i>p</i>-Neighbor <i>k</i>-Center Problem.
Inf. Process. Lett., 1998

Approximation Algorithms for Multiple Sequence Alignment Under a Fixed Evolutionary Tree.
Discret. Appl. Math., 1998

A New Bound for the 2-Edge Connected Subgraph Problem.
Proceedings of the Integer Programming and Combinatorial Optimization, 1998

1997
An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems.
Algorithmica, 1997

Buy-at-Bulk Network Design: Approximating the Single-Sink Edge Installation Problem.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

A Fast Approximation Algorithm for Maximum-Leaf Spanning Tree.
Proceedings of the 1997 International Symposium on Parallel Architectures, 1997

Parallelizing Elimination Orders with Linear Fill.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

Improved results on service-constrained network design problems.
Proceedings of the Network Design: Connectivity and Facilities Location, 1997

Network improvement problems.
Proceedings of the Network Design: Connectivity and Facilities Location, 1997

Banishing Bias from Consensus Sequences.
Proceedings of the Combinatorial Pattern Matching, 8th Annual Symposium, 1997

1996
Spanning Trees - Short or Small.
SIAM J. Discret. Math., 1996

Service-Constrained Network Design Problems.
Nord. J. Comput., 1996

Nonoverlapping Local Alignments (weighted Independent Sets of Axis-parallel Rectangles).
Discret. Appl. Math., 1996

The Constrained Minimum Spanning Tree Problem (Extended Abstract).
Proceedings of the Algorithm Theory, 1996

A Constant-factor Approximation Algorithm for the <i>k</i> MST Problem (Extended Abstract).
Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, 1996

1995
When Trees Collide: An Approximation Algorithm for the Generalized Steiner Problem on Networks.
SIAM J. Comput., 1995

A Nearly Best-Possible Approximation Algorithm for Node-Weighted Steiner Trees.
J. Algorithms, 1995

An Approximate Max-Flow Min-Cut Relation for Unidirected Multicommodity Flow, with Applications.
Comb., 1995

Non-Overlapping Local Alignments (Weighted Independent Sets of Axis Parallel Rectangles).
Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

David P. Williamson: An Approximation Algorithm for Minimum-Cost Vertex-Connectivity Problems.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Of Mice and Men: Algorithms for Evolutionary Distances Between Genomes with Translocation.
Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 1995

Computing Similarity between RNA Strings.
Proceedings of the Combinatorial Pattern Matching, 6th Annual Symposium, 1995

Design Strategies for Optimal Multiplier Circuits.
Proceedings of the 12th Symposium on Computer Arithmetic (ARITH-12 '95), 1995

1994
A Primal-Dual Approximation Algorithm for the Steiner Forest Problem.
Inf. Process. Lett., 1994

Rapid Rumor Ramification: Approximating the minimum broadcast time (Extended Abstract)
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
Many birds with one stone: multi-objective approximation algorithms.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

When cycles collapse: A general approximation technique for constrained two-connectivity problems.
Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29, 1993

1992
An optimal algorithm to solve the all-pair shortest path problem on interval graphs.
Networks, 1992

Generalized Vertex Covering in Interval Graphs.
Discret. Appl. Math., 1992

Approximation Through Local Optimality: Designing Networks with Small Degree.
Proceedings of the Foundations of Software Technology and Theoretical Computer Science, 1992

1991
Ordering Problems Approximated: Single-Processor Scheduling and Interval Graph Completion.
Proceedings of the Automata, Languages and Programming, 18th International Colloquium, 1991

1990
Approximation through Multicommodity Flow
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990


  Loading...