57 citations · 154 across the 36 of their papers we have counts for
Showing 2021 · cs.DSShow all
3 papers · 2 filters
cs.DS2021
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…
cs.DS2021
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…
cs.DS2021
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…