39 citations · 135 across the 18 of their papers we have counts for
3 papers · 2 filters
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…