39 citations · 135 across the 18 of their papers we have counts for
23 papers
Learning-Augmented Online Packet Scheduling with Deadlines
Ya-Chun Liang, Clifford Stein, Hao-Ting Wei
The modern network aims to prioritize critical traffic over non-critical traffic and effectively manage traffic flow. This necessitates proper buffer management to prevent the loss…
Scheduling with Speed Predictions
Eric Balkanski, Tingting Ou, Clifford Stein +1
Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, ver…
Estimating the Longest Increasing Subsequence in Nearly Optimal Time
Alexandr Andoni, Negev Shekel Nosatzki, Sandip Sinha +1
Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length can be computed exactly i…
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…
Incremental Edge Orientation in Forests
Michael A. Bender, Tsvi Kopelowitz, William Kuszmaul +2
For any forest it is possible to orient the edges so that no vertex in has out-degree greater than . This paper considers the incremental edge-orientation p…
Matching Drivers to Riders: A Two-stage Robust Approach
Omar El Housni, Vineet Goyal, Oussama Hanguir +1
Matching demand (riders) to supply (drivers) efficiently is a fundamental problem for ride-sharing platforms who need to match the riders (almost) as soon as the request arrives wi…