57 citations · 154 across the 36 of their papers we have counts for
40 papers
Optimal Decision Tree and Adaptive Submodular Ranking with Noisy Outcomes
Su Jia, Fatemeh Navidi, Viswanath Nagarajan +1
In pool-based active learning, the learner is given an unlabeled data set and aims to efficiently learn the unknown hypothesis by querying the labels of the data points. This can b…
Instance-specific linear relaxations of semidefinite optimization problems
Daniel de Roux, Robert Carr, R. Ravi
We introduce a generic technique to obtain linear relaxations of semidefinite programs with provable guarantees based on the commutativity of the constraint and the objective matri…
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…