3 papers
cs.DS2026
A Faster Directed Single-Source Shortest Path Algorithm
Ran Duan, Xiao Mao, Xinkai Shu +1
This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\s…
cs.DS2025
Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
Ran Duan, Jiayi Mao, Xiao Mao +2
We give a deterministic -time algorithm for single-source shortest paths (SSSP) on directed graphs with real non-negative edge weights in the comparison-addition m…
cs.GT2025
The Long Arm of Nashian Allocation in Online -Mean Welfare Maximization
Zhiyi Huang, Chui Shan Lee, Xinkai Shu +1
We study the online allocation of divisible items to agents with additive valuations for -mean welfare maximization, a problem introduced by Barman, Khan, and Maiti~(2022).…