8 citations · 11 across the 8 of their papers we have counts for
8 papers
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…
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).…
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…
Online Matching Meets Sampling Without Replacement
Zhiyi Huang, Chui Shan Lee, Jianqiao Lu +1
Sampling without replacement is a natural online rounding strategy for converting fractional bipartite matching into an integral one. In Online Bipartite Matching, we can use the B…
A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
Ran Duan, Jiayi Mao, Xinkai Shu +1
In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time $O(m\sqrt{\log n \cdot…
Online Nash Welfare Maximization Without Predictions
Zhiyi Huang, Minming Li, Xinkai Shu +1
The maximization of Nash welfare, which equals the geometric mean of agents' utilities, is widely studied because it balances efficiency and fairness in resource allocation problem…
The Power of Multiple Choices in Online Stochastic Matching
Zhiyi Huang, Xinkai Shu, Shuyi Yan
We study the power of multiple choices in online stochastic matching. Despite a long line of research, existing algorithms still only consider two choices of offline neighbors for…
Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program
Zhiyi Huang, Xinkai Shu
We study the online stochastic matching problem. Consider a bipartite graph with offline vertices on one side, and with i.i.d.online vertices on the other side. The offline vertice…