57 citations · 154 across the 36 of their papers we have counts for
29 papers · 1 filter
Approximation algorithms for Steiner Tree Augmentation Problems
R. Ravi, Weizhong Zhang, Michael Zlatin
In the Steiner Tree Augmentation Problem (STAP), we are given a graph , a set of terminals , and a Steiner tree spanning . The edges $L := E \setmi…
Unit Perturbations in Budgeted Spanning Tree Problems
Hassene Aissi, Solal Attias, Da Qi Chen +1
The minimum spanning tree of a graph is a well-studied structure that is the basis of countless graph theoretic and optimization problem. We study the minimum spanning tree (MST) p…
On Small-Depth Tree Augmentations
Ojas Parekh, R. Ravi, Michael Zlatin
We study the Weighted Tree Augmentation Problem for general link costs. We show that the integrality gap of the ODD-LP relaxation for the (weighted) Tree Augmentation Problem for a…
Using Predicted Weights for Ad Delivery
Thomas Lavastida, Benjamin Moseley, R. Ravi +1
We study the performance of a proportional weights algorithm for online capacitated bipartite matching modeling the delivery of impression ads. The algorithm uses predictions on th…
A simple proof of the Moore-Hodgson Algorithm for minimizing the number of late jobs
Joseph Cheriyan, R. Ravi, Martin Skutella
The Moore-Hodgson Algorithm minimizes the number of late jobs on a single machine. That is, it finds an optimal schedule for the classical problem . Several proof…
An Optimal Rounding for Half-Integral Weighted Minimum Strongly Connected Spanning Subgraph
D Ellis Hershkowitz, Gregory Kehne, R. Ravi
In the weighted minimum strongly connected spanning subgraph (WMSCSS) problem we must purchase a minimum-cost strongly connected spanning subgraph of a digraph. We show that half-i…
Downgrading to Minimize Connectivity
Hassene Aissi, Da Qi Chen, R. Ravi
We study the problem of interdicting a directed graph by deleting nodes with the goal of minimizing the local edge connectivity of the remaining graph from a given source to a sink…
Inventory Routing Problem with Facility Location
Yang Jiao, R. Ravi
We study problems that integrate depot location decisions along with the inventory routing problem of serving clients from these depots over time balancing the costs of routing veh…
Prepare for the Expected Worst: Algorithms for Reconfigurable Resources Under Uncertainty
D Ellis Hershkowitz, R. Ravi, Sahil Singla
In this paper we study how to optimally balance cheap inflexible resources with more expensive, reconfigurable resources despite uncertainty in the input problem. Specifically, we…
Approximation Algorithms for Replenishment Problems with Fixed Turnover Times
Thomas Bosman, Martijn van Ee, Yang Jiao +3
We introduce and study a class of optimization problems we coin replenishment problems with fixed turnover times: a very natural model that has received little attention in the lit…
Coloring Down: -approximation for special cases of the weighted tree augmentation problem
Jennifer Iglesias, R. Ravi
In this paper, we investigate the weighted tree augmentation problem (TAP), where the goal is to augment a tree with a minimum cost set of edges such that the graph becomes two edg…
Single-sink Fractionally Subadditive Network Design
Guru Guruganesh, Jennifer Iglesias, R. Ravi +1
We study a generalization of the Steiner tree problem, where we are given a weighted network together with a collection of subsets of its vertices and a root . We wish t…
Shorter tours and longer detours: Uniform covers and a bit beyond
Arash Haddadan, Alantha Newman, R. Ravi
Motivated by the well known four-thirds conjecture for the traveling salesman problem (TSP), we study the problem of {\em uniform covers}. A graph has an -uniform cove…
Algorithms for Automatic Ranking of Participants and Tasks in an Anonymized Contest
Yang Jiao, R. Ravi, Wolfgang Gatterbauer
We introduce a new set of problems based on the Chain Editing problem. In our version of Chain Editing, we are given a set of anonymous participants and a set of undisclosed tasks…
Plane Gossip: Approximating rumor spread in planar graphs
Jennifer Iglesias, Rajmohan Rajaraman, R Ravi +1
We study the design of schedules for multi-commodity multicast; we are given an undirected graph and a collection of source destination pairs, and the goal is to schedule a min…
LAST but not Least: Online Spanners for Buy-at-Bulk
Anupam Gupta, R. Ravi, Kunal Talwar +1
The online (uniform) buy-at-bulk network design problem asks us to design a network, where the edge-costs exhibit economy-of-scale. Previous approaches to this problem used tree- e…
Graph-TSP from Steiner Cycles
Satoru Iwata, Alantha Newman, R. Ravi
We present an approach for the traveling salesman problem with graph metric based on Steiner cycles. A Steiner cycle is a cycle that is required to contain some specified subset of…
A 9/7-Approximation Algorithm for Graphic TSP in Cubic Bipartite Graphs
Jeremy Karp, R. Ravi
We prove new results for approximating Graphic TSP. Specifically, we provide a polynomial-time \frac{9}{7}-approximation algorithm for cubic bipartite graphs and a (\frac{9}{7}+\fr…
Approximation Algorithms for Online Weighted Rank Function Maximization under Matroid Constraints
Niv Buchbinder, Joseph, Naor +2
Consider the following online version of the submodular maximization problem under a matroid constraint: We are given a set of elements over which a matroid is defined. The goal is…
Geometry of Online Packing Linear Programs
Marco Molinaro, R. Ravi
We consider packing LP's with rows where all constraint coefficients are normalized to be in the unit interval. The n columns arrive in random order and the goal is to set the…
Iterative rounding approximation algorithms for degree-bounded node-connectivity network design
Takuro Fukunaga, Zeev Nutov, R. Ravi
We consider the problem of finding a minimum edge cost subgraph of a graph satisfying both given node-connectivity requirements and degree upper bounds on nodes. We present an iter…
The Query-commit Problem
Marco Molinaro, R. Ravi
In the query-commit problem we are given a graph where edges have distinct probabilities of existing. It is possible to query the edges of the graph, and if the queried edge exists…
Minimum Makespan Multi-vehicle Dial-a-Ride
Inge Li Goertz, Viswanath Nagarajan, R. Ravi
Dial a ride problems consist of a metric space (denoting travel time between vertices) and a set of m objects represented as source-destination pairs, where each object requires to…
Approximation Algorithms for Correlated Knapsacks and Non-Martingale Bandits
Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro +1
In the stochastic knapsack problem, we are given a knapsack of size B, and a set of jobs whose sizes and rewards are drawn from a known probability distribution. However, we know t…