Publications

Authors are listed in alphabetical order following the traditions of theoretical computer science, unless stated otherwise.

2026

  1. A Faster Directed Single-Source Shortest Path Algorithm
    Ran Duan, Xiao Mao, Xinkai Shu, and Longhui Yin
    In Proceedings of the 53rd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2026), London, UK, Jul 2026
    arXiv DOI scholar 1

2025

  1. The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization
    Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang
    In Proceedings of the 52nd EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2025), Aarhus, Denmark, Jul 2025
    arXiv DOI scholar 5
  2. Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
    Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin
    In Proceedings of the 57th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2025), Prague, Czech Republic, Jun 2025
    Best Paper Award. Accepted to the Journal of the ACM
    arXiv DOI scholar 57

2024

  1. Online Matching Meets Sampling Without Replacement
    Zhiyi Huang, Chui Shan Lee, Jianqiao Lu, and Xinkai Shu
    In Proceedings of the 20th Conference on Web and Internet Economics (WINE 2024), Edinburgh, United Kingdom, Dec 2024
    arXiv DOI scholar 2

2023

  1. Online Nash Welfare Maximization Without Predictions
    Zhiyi Huang, Minming Li, Xinkai Shu, and Tianze Wei
    In Proceedings of the 19th Conference on Web and Internet Economics (WINE 2023), Shanghai, China, Dec 2023
    arXiv DOI scholar 12
  2. A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs
    Ran Duan, Jiayi Mao, Xinkai Shu, and Longhui Yin
    In Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023), Santa Cruz, USA, Nov 2023
    arXiv DOI scholar 21

2022

  1. The Power of Multiple Choices in Online Stochastic Matching
    Zhiyi Huang, Xinkai Shu, and Shuyi Yan
    In Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2022), Rome, Italy, Jun 2022
    arXiv DOI scholar 58

2021

  1. Online Stochastic Matching, Poisson Arrivals, and the Natural Linear Program
    Zhiyi Huang and Xinkai Shu
    In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2021), Rome, Italy (virtually), Jun 2021
    arXiv DOI scholar 69