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.DS2025
Covering Approximate Shortest Paths with DAGs
Sepehr Assadi, Gary Hoppenworth, Nicole Wein
We define and study analogs of probabilistic tree embedding and tree cover for directed graphs. We define the notion of a DAG cover of a general directed graph : a small collect…