Showing cs.DSShow all
2 papers · 1 filter
cs.DS2024
Naively Sorting Evolving Data is Optimal and Robust
George Giakkoupis, Marcos Kiwi, Dimitrios Los
We study sorting in the evolving data model, introduced by [AKMU11], where the true total order changes while the sorting algorithm is processing the input. More precisely, each co…
cs.DS2024
An asymptotically optimal algorithm for generating bin cardinalities
Luc Devroye, Dimitrios Los
In the balls-into-bins setting, balls are thrown uniformly at random into bins. The naïve way to generate the final load vector takes time. However, it is well-known…