23 citations · 129 across the 42 of their papers we have counts for
5 papers · 1 filter
Learning-Augmented Algorithms for Online Steiner Tree
Chenyang Xu, Benjamin Moseley
This paper considers the recently popular beyond-worst-case algorithm analysis model which integrates machine-learned predictions with online algorithm design. We consider the onli…
A Competitive Algorithm for Throughput Maximization on Identical Machines
Benjamin Moseley, Kirk Pruhs, Clifford Stein +1
This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline on identical machines. The main resu…
Faster Matchings via Learned Duals
Michael Dinitz, Sungjin Im, Thomas Lavastida +2
A recent line of research investigates how algorithms can be augmented with machine-learned predictions to overcome worst case lower bounds. This area has revealed interesting algo…
An Efficient Reduction of a Gammoid to a Partition Matroid
Marilena Leichter, Benjamin Moseley, Kirk Pruhs
Our main contribution is a polynomial-time algorithm to reduce a -colorable gammoid to a -colorable partition matroid. It is known that there are gammoids that can not b…
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…