Arrow Research search

Author name cluster

R. Ravi 0001

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

37 papers
1 author row

Possible papers

37

SODA Conference 2023 Conference Paper

Approximation Algorithms for Steiner Tree Augmentation Problems

  • R. Ravi 0001
  • Weizhong Zhang
  • Michael Zlatin

In the Steiner Tree Augmentation Problem (STAP), we are given a graph G = (V, E), a set of terminals R ⊆ V, and a Steiner tree T spanning R. The edges L: = E\E(T) are called links and have non-negative costs. The goal is to augment T by adding a minimum cost set of links, so that there are 2 edge-disjoint paths between each pair of vertices in R. This problem is a special case of the Survivable Network Design Problem, which can be approximated to within a factor of 2 using iterative rounding [13]. We give the first polynomial time algorithm for STAP with approximation ratio better than 2. In particular, we achieve an approximation ratio of (1. 5 + ε). To do this, we employ the Local Search approach of [24] for the Tree Augmentation Problem and generalize their main decomposition theorem from links (of size two) to hyper-links. We also consider the Node-Weighted Steiner Tree Augmentation Problem (NW-STAP) in which the non-terminal nodes have non-negative costs. We seek a cheapest subset S ⊆ V\R so that G[R ∪ S ] is 2-edge-connected. Using a result of Nutov [18], there exists an O (log | R |)-approximation for this problem. We provide an O (log 2 (| R |))-approximation algorithm for NW-STAP using a greedy algorithm leveraging the spider decomposition of optimal solutions.

Details

ICML Conference 2023 Conference Paper

Short-lived High-volume Bandits

  • Su Jia
  • Nishant Oli
  • Ian Anderson 0005
  • Paul Duff
  • Andrew A. Li
  • R. Ravi 0001

Modern platforms leverage randomized experiments to make informed decisions from a given set of alternatives. As a particularly challenging scenario, these alternatives can potentially have (i) high volume, with thousands of new items being released each hour, and (ii) short lifetime, either due to the contents’ transient nature, or some underlying non-stationarity that impels the learner to treat the same item as non-identical copies across time. We consider a multiplay bandits model. In each round a set of $k=n^\rho$ actions that will be available for $w$ rounds arrives, each of whose mean reward is drawn from a fixed known distribution. The learner selects a multiset of $n$ actions at a time. We propose an $\ell$-Layered Sieve Policy that recursively refines the action space for $\ell\leq w$ times. We show that for any given $\rho>0$, with suitable $\ell$, the policy achieves $\tilde O (n^{-\min \{\rho, \frac 12 (1+\frac 1w)^{-1}\}})$ regret. We also complement this result with an $\Omega (n^{-\min \{\rho, \frac 12\}})$ lower bound. We further validate the effectiveness of our Sieve Policy via numerical simulations and a field experiment in a large content card serving platform.

Details

SODA Conference 2023 Conference Paper

Timeliness Through Telephones: Approximating Information Freshness in Vector Clock Models

  • Da Qi Chen
  • Lin An
  • Aidin Niaparast
  • R. Ravi 0001
  • Oleksandr Rudenko

We consider an information dissemination problem where the root node in an undirected graph constantly updates its information. The goal is to keep every other node in the graph as freshly informed about the root as possible. Our synchronous information spreading model uses telephone calls at each time step, in which any node can communicate with at most one neighbor, thus forming a matching over which information is transmitted at each step. We introduce two problems in minimizing two natural objectives (Maximum and Average) of the latency of the root's information at all nodes in the network. After deriving a simple reduction from the maximum rooted latency problem to the well-studied minimum broadcast time problem, we focus on the average rooted latency version. We introduce a natural problem of finding a finite schedule that minimizes the average broadcast time from a root. We show that any average rooted latency scheme induces a solution to this average broadcast problem within a constant factor and conversely, this average broadcast time is within a logarithmic factor of the average rooted latency. Then, we derive a log-squared approximation algorithm for the average broadcast time problem via rounding a time-indexed linear programming relaxation, resulting in a log-cubed approximation for the average latency problem. Surprisingly, we show that using the average broadcast time for average rooted latency introduces a necessary logarithmic factor overhead even in trees. We overcome this hurdle and give a 40-approximation for trees. For this, we design an algorithm to find near-optimal locally-periodic schedules in trees where each vertex receives information from its parent in regular intervals. On the other side, we show how such well-behaved schedules approximate the optimal schedule within a constant factor. * This material is based upon work supported in part by the U. S. Office of Naval Research under award number N00014-21-1-2243 and the Air Force Office of Scientific Research under award number FA9550-20-1-0080.

Details

SoCS Conference 2022 Conference Paper

Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions (Extended Abstract)

  • Nikhil Chandak
  • Kenny Chour
  • Sivakumar Rathinam
  • R. Ravi 0001

We interleave sampling based motion planning methods with pruning ideas from minimum spanning tree algorithms to develop a new approach for solving a Multi-Goal Path Finding (MGPF) problem in high dimensional spaces. The approach alternates between sampling points from selected regions in the search space and de-emphasizing regions that may not lead to good solutions for MGPF. Our approach provides an asymptotic, 2-approximation guarantee for MGPF. We also present extensive numerical results to illustrate the advantages of our proposed approach over uniform sampling in terms of the quality of the solutions found and computation speed.

Details

UAI Conference 2021 Conference Paper

A heuristic for statistical seriation

  • Komal Dhull
  • Jingyan Wang 0001
  • Nihar B. Shah
  • Yuanzhi Li
  • R. Ravi 0001

We study the statistical seriation problem, where the goal is to estimate a matrix whose rows satisfy the same shape constraint after a permutation of the columns. This is a important classical problem, with close connections to statistical literature in permutation-based models and also has wide applications ranging from archaeology to biology. Specifically, we consider the case where the rows are monotonically increasing after an unknown permutation of the columns. Past work has shown that the least-squares estimator is optimal up to logarithmic factors, but efficient algorithms for computing the least-squares estimator remain unknown to date. We approach this important problem from a heuristic perspective. Specifically, we replace the combinatorial permutation constraint by a continuous regularization term, and then use projected gradient descent to obtain a local minimum of the non-convex objective. We show that the attained local minimum is the global minimum in certain special cases under the noiseless setting, and preserves desirable properties under the noisy setting. Simulation results reveal that our proposed algorithm outperforms prior algorithms when (1) the underlying model is more complex than simplistic parametric assumptions such as low-rankedness, or (2) the signal-to-noise ratio is high. Under partial observations, the proposed algorithm requires an initialization, and different initializations may lead to different local minima. We empirically observe that the proposed algorithm yields consistent improvement over the initialization, even though different initializations start with different levels of quality.

Details

SODA Conference 2017 Conference Paper

LAST but not Least: Online Spanners for Buy-at-Bulk

  • Anupam Gupta 0001
  • R. Ravi 0001
  • Kunal Talwar
  • Seeun William Umboh

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-embeddings, giving us randomized algorithms. Moreover, the optimal results with a logarithmic competitive ratio requires the metric on which the network is being built to be known up-front; the competitive ratios then depend on the size of this metric (which could be much larger than the number of terminals that arrive). We consider the buy-at-bulk problem in the least restrictive model where the metric is not known in advance, but revealed in parts along with the demand points seeking connectivity arriving online. For the single sink buy-at-bulk problem, we give a deterministic online algorithm with competitive ratio that is logarithmic in k, the number of terminals that have arrived, matching the lower bound known even for the online Steiner tree problem. In the oblivious case when the buy-at-bulk function used to compute the edge-costs of the network is not known in advance (but is the same across all edges), we give a deterministic algorithm with competitive ratio polylogarithmic in k, the number of terminals. At the heart of our algorithms are optimal constructions for online Light Approximate Shortest-path Trees (LASTs) and spanners, and their variants. We give constructions that have optimal trade-offs in terms of cost and stretch. We also define and give constructions for a new notion of LASTs where the set of roots (in addition to the points) expands over time. We expect these techniques will find applications in other online network-design problems.

Details

FOCS Conference 2012 Conference Paper

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

  • Takuro Fukunaga
  • R. Ravi 0001

We consider the problem of finding a minimum edge cost subgraph of an undirected or a directed graph satisfying given connectivity requirements and degree bounds b(·) on nodes. We present an iterative rounding algorithm for this problem. When the graph is undirected and the connectivity requirements are on the element-connectivity with maximum value k, our algorithm computes a solution that is an O(k)-approximation for the edge cost in which the degree of each node v is at most O(k) · b(v). We also consider the no edge cost case where the objective is to find a subgraph satisfying connectivity requirements and degree bounds. Our algorithm for this case outputs a solution in which the degree of each node v is at most 6·b(v)+O(k 2 ). These algorithms can be extended to other well-studied undirected node-connectivity requirements such as uniform, subset and rooted connectivity. When the graph is directed and the connectivity requirement is k-out-connectivity from a root, our algorithm computes a solution that is a 2-approximation for the edge cost in which the degree of each node v is at most 2 · b(v) + O(k).

Details

FOCS Conference 2011 Conference Paper

Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits

  • Anupam Gupta 0001
  • Ravishankar Krishnaswamy
  • Marco Molinaro 0001
  • R. Ravi 0001

In the stochastic knapsack problem, we are given a knapsack of size B, and a set of items whose sizes and rewards are drawn from a known probability distribution. To know the actual size and reward we have to schedule the item-when it completes, we get to know these values. The goal is to schedule the items (possibly making adaptive decisions based on the sizes seen so far) to maximize the expected total reward of items which successfully pack into the knapsack. We know constant-factor approximations when (i) the rewards and sizes are independent, and (ii) we cannot prematurely cancel items after we schedule them. What if either or both assumptions are relaxed? Related stochastic packing problems are the multi-armed bandit (and budgeted learning) problems, here one is given several arms which evolve in a specified stochastic fashion with each pull, and the goal is to (adaptively) decide which arms to pull, in order to maximize the expected reward obtained after B pulls in total. Much recent work on this problem focuses on the case when the evolution of each arm follows a martingale, i. e. , when the expected reward from one pull of an arm is the same as the reward at the current state. What if the rewards do not form a martingale? In this paper, we give O(1)-approximation algorithms for the stochastic knapsack problem with correlations and/or cancellations. Extending the ideas developed here, we give O(1)-approximations for MAB problems without the martingale assumption. Indeed, we can show that previously proposed linear programming relaxations for these problems have large integrality gaps. So we propose new time-indexed LP relaxations, using a decomposition and "gap-filling" approach, we convert these fractional solutions to distributions over strategies, and then use the LP values and the time ordering information from these strategies to devise randomized adaptive scheduling algorithms.

Details

SODA Conference 2010 Conference Paper

Tree Embeddings for Two-Edge-Connected Network Design

  • Anupam Gupta 0001
  • Ravishankar Krishnaswamy
  • R. Ravi 0001

The group Steiner problem is a classical network design problem where we are given a graph and a collection of groups of vertices, and want to build a min-cost subgraph that connects the root vertex to at least one vertex from each group. What if we wanted to build a subgraph that two-edge-connects the root to each group—that is, for every group g ⊆ V, the subgraph should contain two edge-disjoint paths from the root to some vertex in g? What if we wanted the two edge-disjoint paths to end up at distinct vertices in the group, so that the loss of a single member of the group would not destroy connectivity? In this paper, we investigate tree-embedding techniques that can be used to solve these and other 2-edge-connected network design problems. We illustrate the potential of these techniques by giving poly-logarithmic approximation algorithms for two-edge-connected versions of the group Steiner, connected facility location, buy-at-bulk, and the k -MST problems.

Details

FOCS Conference 2005 Conference Paper

How to Pay, Come What May: Approximation Algorithms for Demand-Robust Covering Problems

  • Kedar Dhamdhere
  • Vineet Goyal
  • R. Ravi 0001
  • Mohit Singh

Robust optimization has traditionally focused on uncertainty in data and costs in optimization problems to formulate models whose solutions will be optimal in the worst-case among the various uncertain scenarios in the model. While these approaches may be thought of defining data- or cost-robust problems, we formulate a new "demand-robust" model motivated by recent work on two-stage stochastic optimization problems. We propose this in the framework of general covering problems and prove a general structural lemma about special types of first-stage solutions for such problems: there exists a first-stage solution that is a minimal feasible solution for the union of the demands for some subset of the scenarios and its objective function value is no more than twice the optimal. We then provide approximation algorithms for a variety of standard discrete covering problems in this setting, including minimum cut, minimum multi-cut, shortest paths, Steiner trees, vertex cover and un-capacitated facility location. While many of our results draw from rounding approaches recently developed for stochastic programming problems, we also show new applications of old metric rounding techniques for cut problems in this demand-robust setting.

Details

FOCS Conference 2004 Conference Paper

An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design

  • Anupam Gupta 0001
  • R. Ravi 0001
  • Amitabh Sinha

Real-world networks often need to be designed under uncertainty, with only partial information and predictions of demand available at the outset of the design process. The field of stochastic optimization deals with such problems where the forecasts are specified in terms of probability distributions of future data. In this paper, we broaden the set of models as well as the techniques being considered for approximating stochastic optimization problems. For example, we look at stochastic models where the cost of the elements is correlated to the set of realized demands, and risk-averse models where upper bounds are placed on the amount spent in each of the stages. These generalized models require new techniques, and our solutions are based on a novel combination of the primal-dual method truncated based on optimal LP relaxation values, followed by a tree-rounding stage. We use these to give constant-factor approximation algorithms for the stochastic Steiner tree and single sink network design problems in these generalized models.

Details

STOC Conference 2004 Conference Paper

Boosted sampling: approximation algorithms for stochastic optimization

  • Anupam Gupta 0001
  • Martin Pál
  • R. Ravi 0001
  • Amitabh Sinha

Several combinatorial optimization problems choose elements to minimize the total cost of constructing a feasible solution that satisfies requirements of clients. In the Steiner Tree problem, for example, edges must be chosen to connect terminals (clients); in Vertex Cover, vertices must be chosen to cover edges (clients); in Facility Location, facilities must be chosen and demand vertices (clients) connected to these chosen facilities. We consider a stochastic version of such a problem where the solution is constructed in two stages: Before the actual requirements materialize, we can choose elements in a first stage. The actual requirements are then revealed, drawn from a pre-specified probability distribution π thereupon, some more elements may be chosen to obtain a feasible solution for the actual requirements. However, in this second (recourse) stage, choosing an element is costlier by a factor of σ> 1. The goal is to minimize the first stage cost plus the expected second stage cost.We give a general yet simple technique to adapt approximation algorithms for several deterministic problems to their stochastic versions via the following method. First stage: Draw σ independent sets of clients from the distribution π and apply the approximation algorithm to construct a feasible solution for the union of these sets. Second stage: Since the actual requirements have now been revealed, augment the first-stage solution to be feasible for these requirements. We use this framework to derive constant factor approximations for stochastic versions of Vertex Cover, Steiner Tree and Uncapacitated Facility Location for arbitrary distributions π in one fell swoop. For special (product) distributions, we obtain additional and improved results. Our techniques adapt and use the notion of strict cost-shares introduced in [5].

Details

FOCS Conference 1997 Conference Paper

Parallelizing Elimination Orders with Linear Fill

  • Claudson F. Bornstein
  • Bruce M. Maggs
  • Gary L. Miller
  • R. Ravi 0001

This paper presents an algorithm for finding parallel elimination orders for Gaussian elimination. Viewing a system of equations as a graph, the algorithm can be applied directly to interval graphs and chordal graphs. For general graphs, the algorithm can be used to parallelize the order produced by some other heuristic such as minimum degree. In this case, the algorithm is applied to the chordal completion that the heuristic generates from the input graph. In general, the input to the algorithm is a chordal graph G with n nodes and m edges. The algorithm produces an order with height at most O(log/sup 3/ n) times optimal, fill at most O(m), and work at most O(W*(G)), where W*(G) is the minimum possible work over all elimination orders for G. Experimental results show that when applied after some other heuristic, the increase in work and fill is usually small. In some instances the algorithm obtains an order that is actually better, in terms of work and fill, than the original one. We also present an algorithm that produces an order with a factor of log n less height, but with a factor of O(/spl radic/log n) more fill.

Details

FOCS Conference 1994 Conference Paper

Rapid Rumor Ramification: Approximating the minimum broadcast time (Extended Abstract)

  • R. Ravi 0001

Given an undirected graph representing a network of processors, and a source node containing a message that must be broadcast to all the nodes, find a scheme that accomplishes the broadcast in the minimum number of time steps. At each time step, any processor that has received the message is allowed to communicate the message to at most one of its neighbors in the network, i. e. can communicate via a telephone call to a neighbor. This has been termed the minimum broadcast time problem under the telephone model and is known to be NP-complete. The minimum broadcast time in a graph is closely related to the poise of the graph. The poise of a tree is defined to be the quantity (maximum degree of any node in the tree+diameter of the tree). The poise of a graph is the minimum poise of any of its spanning trees. Computing the poise of a graph is shown to be NP-hard and an algorithm for computing a spanning tree of approximately minimum poise is derived. This algorithm is then used to derive an O(log/sup 2/n/log log n)-approximation for the minimum broadcast time problem on an n-node graph. Our algorithm extends to many generalizations of the problem such as the multicast problem, a telephone model allowing conference calls, and to the closely related minimum gossip time problem. >

Details

FOCS Conference 1990 Conference Paper

Approximation through Multicommodity Flow

  • Philip N. Klein
  • Ajit Agrawal
  • R. Ravi 0001
  • Satish Rao

The first approximate max-flow-min-cut theorem for general multicommodity flow is proved. It is used to obtain approximation algorithms for minimum deletion of clauses of a 2-CNF identical to formula, via minimization problems, and other problems. Also presented are approximation algorithms for chordalization of a graph and for register sufficiency that are based on undirected and directed node separators. >

Details
v2026.09.13