3 papers
cs.DS2025
Improved Online Sorting
Jubayer Nirjhor, Nicole Wein
We study the online sorting problem, where real numbers arrive in an online fashion, and the algorithm must immediately place each number into an array of size $(1+\varepsilon)…
cs.DS2025
Settling Weighted Token Swapping up to Algorithmic Barriers
Nicole Wein, Guanyu Tony Zhang
We study the weighted token swapping problem, in which we are given a graph on vertices, weighted tokens, an initial assignment of one token to each vertex, and a final ass…
cs.DS2024
Edge-Minimum Walk of Modular Length in Polynomial Time
Antoine Amarilli, Benoît Groz, Nicole Wein
We study the problem of finding, in a directed graph, an st-walk of length r mod q which is edge-minimum, i.e., uses the smallest number of distinct edges. Despite the vast literat…