5 papers
A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
Kuowen Chen, Nicole Wein, Yiran Zhang
Given a graph and a pair of terminals , , the next-to-shortest path problem asks for an (simple) path that is shortest among all not shortest paths…
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)…
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…
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…
Improved Hardness-of-Approximation for Token Swapping
Sam Hiken, Nicole Wein
We study the token swapping problem, in which we are given a graph with an initial assignment of one distinct token to each vertex, and a final desired assignment (again with one t…