DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.81

A Faster Directed Single-Source Shortest Path Algorithm

Authors: Ran Duan, Xiao Mao, Xinkai Shu, and Longhui Yin

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

This paper presents a new deterministic algorithm for the single-source shortest paths (SSSP) problem on real non-negative edge-weighted directed graphs, with running time O(m√{log n} + √{mnlog nlog log n}), which is O(m√{log nlog log n}) for sparse graphs. This improves the recent breakthrough result of O(m log^{2/3} n) time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025].

Cite as

Ran Duan, Xiao Mao, Xinkai Shu, and Longhui Yin. A Faster Directed Single-Source Shortest Path Algorithm. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 81:1-81:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duan_et_al:LIPIcs.ICALP.2026.81,
  author =	{Duan, Ran and Mao, Xiao and Shu, Xinkai and Yin, Longhui},
  title =	{{A Faster Directed Single-Source Shortest Path Algorithm}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{81:1--81:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.81},
  URN =		{urn:nbn:de:0030-drops-264706},
  doi =		{10.4230/LIPIcs.ICALP.2026.81},
  annote =	{Keywords: Shortest Paths, Graph Algorithms}
}

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2025.98

The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization

Authors: Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

We study the online allocation of divisible items to n agents with additive valuations for p-mean welfare maximization, a problem introduced by Barman, Khan, and Maiti (2022). Our algorithmic and hardness results characterize the optimal competitive ratios for the entire spectrum of -∞ ≤ p ≤ 1. Surprisingly, our improved algorithms for all p ≤ (1)/(log n) are simply the greedy algorithm for the Nash welfare, supplemented with two auxiliary components to ensure all agents have non-zero utilities and to help a small number of agents with low utilities. In this sense, the long arm of Nashian allocation achieves near-optimal competitive ratios not only for Nash welfare but also all the way to egalitarian welfare.

Cite as

Zhiyi Huang, Chui Shan Lee, Xinkai Shu, and Zhaozi Wang. The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 98:1-98:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ICALP.2025.98,
  author =	{Huang, Zhiyi and Lee, Chui Shan and Shu, Xinkai and Wang, Zhaozi},
  title =	{{The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{98:1--98:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.98},
  URN =		{urn:nbn:de:0030-drops-234754},
  doi =		{10.4230/LIPIcs.ICALP.2025.98},
  annote =	{Keywords: Online Algorithms, Fair Division, Nash Welfare}
}

Search Results

Documents authored by Shu, Xinkai

A Faster Directed Single-Source Shortest Path Algorithm

Abstract

Cite as

The Long Arm of Nashian Allocation in Online p-Mean Welfare Maximization

Abstract

Cite as

Thanks for your feedback!

Could not send message