Fetching the paper…
Reading the bibliography…
We explore the fundamental problem of sorting through the lens of learning-augmented algorithms, where algorithms can leverage possibly erroneous predictions to improve their efficiency.
A new representation for linear lists
L. J. Guibas, E. M. McCreight, M. F. Plass, and J. R. Roberts · 1977
Earlier work this paper cites.
Best sorting algorithm for nearly sorted lists
C. R. Cook and D. J. Kim · 1980
Earlier work this paper cites.
Measures of presortedness and optimal sorting algorithms
H. Mannila · 1985
Earlier work this paper cites.
A survey of adaptive sorting algorithms
V. Estivill-Castro and D. Wood · 1992
Earlier work this paper cites.
A decision-theoretic generalization of on-line learning and an application to boosting
Y. Freund and R. E. Schapire · 1997
Earlier work this paper cites.
[Python-Dev] Sorting
T. Peters · 2002
Earlier work this paper cites.
Aggregating inconsistent information: Ranking and clustering
N. Ailon, M. Charikar, and A. Newman · 2008
Earlier work this paper cites.
Noisy sorting without resampling
M. Braverman and E. Mossel · 2008
Earlier work this paper cites.
The case for learned index structures
T. Kraska, A. Beutel, E. H. Chi, J. Dean, and N. Polyzotis · 2018
Earlier work this paper cites.
Nearly-optimal mergesorts: Fast, practical sorting methods that optimally adapt to existing runs
J. I. Munro and S. Wild · 2018
Earlier work this paper cites.
Improving online algorithms via ML predictions
M. Purohit, Z. Svitkina, and R. Kumar · 2018
Earlier work this paper cites.
Optimal sorting with persistent comparison errors
B. Geissmann, S. Leucci, C. Liu, and P. Penna · 2019
Earlier work this paper cites.
Online algorithms for rent-or-buy with expert advice
S. Gollapudi and D. Panigrahi · 2019
Earlier work this paper cites.
SageDB: A learned database system
T. Kraska, M. Alizadeh, A. Beutel, E. H. Chi, A. Kristo, G. Leclerc, S. Madden, H. Mao, and V. Nathan · 2019
Earlier work this paper cites.
Online computation with untrusted advice
S. Angelopoulos, C. Dürr, S. Jin, S. Kamali, and M. P. Renault · 2020
Earlier work this paper cites.
Online linear optimization with many hints
A. Bhaskara, A. Cutkosky, R. Kumar, and M. Purohit · 2020
Earlier work this paper cites.
The case for a learned sorting algorithm
A. Kristo, K. Vaidya, U. Çetintemel, S. Misra, and T. Kraska · 2020
Cited alongside, same era.
Online scheduling via learned weights
S. Lattanzi, T. Lavastida, B. Moseley, and S. Vassilvitskii · 2020
Cited alongside, same era.
Scheduling with predictions and the price of misprediction
M. Mitzenmacher · 2020
Cited alongside, same era.
Near-optimal bounds for online caching with machine learned advice
D. Rohatgi · 2020
Cited alongside, same era.
Online algorithms for multi-shop ski rental with machine learned advice
S. Wang, J. Li, and S. Wang · 2020
Cited alongside, same era.
Better and simpler learning-augmented online caching
A. Wei · 2020
Cited alongside, same era.
Learning-augmented weighted paging
N. Bansal, C. Coester, R. Kumar, M. Purohit, and E. Vee · 2022
Later among the works it cites.
Faster fundamental graph algorithms via learned predictions
J. Y. Chen, S. Silwal, A. Vakilian, and F. Zhang · 2022
Later among the works it cites.
Algorithms with prediction portfolios
M. Dinitz, S. Im, T. Lavastida, B. Moseley, and S. Vassilvitskii · 2022
Later among the works it cites.
Learning-augmented k-means clustering
J. Ergun, Z. Feng, S. Silwal, D. P. Woodruff, and S. Zhou · 2022
Later among the works it cites.
Learning augmented binary search trees
H. Lin, T. Luo, and D. P. Woodruff · 2022
Later among the works it cites.
Permutation predictions for non-clairvoyant scheduling
A. Lindermayr and N. Megow · 2022
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Online facility location with multiple advice
M. Almanza, F. Chierichetti, S. Lattanzi, A. Panconesi, and G. Re · 2021
Cited alongside, same era.
Learning-augmented dynamic power management with multiple states via new ski rental bounds
A. Antoniadis, C. Coester, M. Eliás, A. Polak, and B. Simon · 2021
Cited alongside, same era.
Flow time scheduling with uncertain processing time
Y. Azar, S. Leonardi, and N. Touitou · 2021
Cited alongside, same era.
Faster matchings via learned duals
M. Dinitz, S. Im, T. Lavastida, B. Moseley, and S. Vassilvitskii · 2021
Cited alongside, same era.
Online paging with a vanishing regret
Y. Emek, S. Kutten, and Y. Shi · 2021
Cited alongside, same era.
Generalized sorting with predictions
P. Lu, X. Ren, E. Sun, and Y. Zhang · 2021
Cited alongside, same era.
Algorithms with predictions
M. Mitzenmacher and S. Vassilvitskii · 2022
Later among the works it cites.
Discrete-convex-analysis-based framework for warm-starting algorithms with predictions
S. Sakaue and T. Oki · 2022
Later among the works it cites.
Population, total, 2023
World Bank · 2022
Later among the works it cites.
Mixing predictions for online metric algorithms
A. Antoniadis, C. Coester, M. Eliás, A. Polak, and B. Simon · 2023
Closest in time.
Learning-augmented b-trees, 2023
X. Cao, J. Chen, L. Chen, C. Lambert, R. Peng, and D. Sleator · 2023
Closest in time.
Predictive flows for faster ford-fulkerson
S. Davies, B. Moseley, S. Vassilvitskii, and Y. Wang · 2023
Closest in time.
Sorting and hypergraph orientation under uncertainty with predictions
T. Erlebach, M. S. de Lima, N. Megow, and J. Schlöter · 2023
Closest in time.
Optimal bounds for noisy sorting
Y. Gu and Y. Xu · 2023
Closest in time.
Faster sorting algorithms discovered using deep reinforcement learning
D. J. Mankowitz, A. Michi, A. Zhernov, M. Gelmi, M. Selvi, C. Paduraru, E. Leurent, S. Iqbal, J.-B. Lespiau, A. Ahern, T. Köppe, K. Millikin, S. Gaffney, S. Elster, J. Broshear, C. Gamble, K. Milan, R. Tung, M. Hwang, T. Cemgil, M. Barekatain, Y. Li, A. Mandhane, T. Hubert, J. Schrittwieser, D. Hassabis, P. Kohli, M. Riedmiller, O. Vinyals, and D. Silver · 2023
Closest in time.