7 papers · 1 filter
Incremental Strongly Connected Components with Predictions
Ronald Deng, Samuel McCauley, Aidin Niaparast +5
Algorithms with predictions is a growing area that aims to leverage machine-learned predictions to design faster beyond-worst-case algorithms. In this paper, we use this framework…
Incremental Approximate Single-Source Shortest Paths with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +2
The algorithms-with-predictions framework has been used extensively to develop online algorithms with improved beyond-worst-case competitive ratios. Recently, there is growing inte…
Incremental Topological Ordering and Cycle Detection with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +1
This paper leverages the framework of algorithms-with-predictions to design data structures for two fundamental dynamic graph problems: incremental topological ordering and cycle d…
Online List Labeling with Predictions
Samuel McCauley, Benjamin Moseley, Aidin Niaparast +1
A growing line of work shows how learned predictions can be used to break through worst-case barriers to improve the running time of an algorithm. However, incorporating prediction…
Telescoping Filter: A Practical Adaptive Filter
David J. Lee, Samuel McCauley, Shikha Singh +1
Filters are fast, small and approximate set membership data structures. They are often used to filter out expensive accesses to a remote set S for negative queries (that is, a quer…
The Online Event-Detection Problem
Michael A. Bender, Jonathan W. Berry, Martin Farach-Colton +5
Given a stream , a -heavy hitter is an item that occurs at least times in . The problem of finding heavy-hitters has been extensively stu…