10 citations · 19 across the 9 of their papers we have counts for
Showing 2019Show all
3 papers · 1 filter
cs.DS2019
Achieving Optimal Backlog in the Vanilla Multi-Processor Cup Game
William Kuszmaul
In each step of the -processor cup game on cups, a filler distributes up to units of water among the cups, subject only to the constraint that no cup receives more than…
cs.DS2019★ 10 cited
Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
William Kuszmaul
Dynamic time warping distance (DTW) is a widely used distance measure between time series. The best known algorithms for computing DTW run in near quadratic time, and conditional l…
cs.DS2019
Achieving Optimal Backlog in Multi-Processor Cup Games
Michael A. Bender, Martin Farach-Colton, William Kuszmaul
The single- and multi- processor cup games can be used to model natural problems in areas such as processor scheduling, deamortization, and buffer management. At the beginning of t…