57 citations · 154 across the 36 of their papers we have counts for
4 papers · 1 filter
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…
S: A Heuristic Information-Based Approximation Framework for Multi-Goal Path Finding
Kenny Chour, Sivakumar Rathinam, Ramamoorthi Ravi
We combine ideas from uni-directional and bi-directional heuristic search, and approximation algorithms for the Traveling Salesman Problem, to develop a novel framework for a Multi…