PG电子游戏

图论算法、数据结构、近似和随机算法、计算复杂性

PG电子游戏-博彩电子游戏推荐 ：

计算理论（本科生），2015~2024春

算法设计与分析（研究生），2015~2024秋

现代信息技术理论与实践（本科生），2016夏，2017夏

计算机入门（本科生），2020秋，2021秋

萨尔大学（德国）：

2012夏，高等图论算法（研究生），与Jens M. Schmidt 和 Magnus Wahlström 合讲

PC Member of FAW 2018, FAW 2019, ISAAC 2019, FAW 2020, ICALP 2021, ESA 2021, SOSA 2023, SODA 2024, ITCS 2024

Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election

Yi-Jun Chang, Ran Duan, Shunhua Jiang

ACM Transactions on Algorithms, 19(4), Article 33

arXiv

Connectivity Oracles for Graphs Subject to Vertex Failures

Ran Duan, Seth Pettie

SIAM J. Comput., 49(6), 1363–1396

arXiv

Scaling Algorithms for Weighted Matching in General Graphs

Ran Duan, Seth Pettie, Hsin-Hao Su

ACM Transactions on Algorithms 14(1), Article 8, 2018

arXiv

A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market

Ran Duan, Kurt Mehlhorn

Journal version: Information and Computation, Volume 243, 112-132, 2015

arXiv

Linear-Time Approximation for Maximum Weight Matching

Ran Duan, Seth Pettie

Journal of the ACM, 61(1):1-23, 2014

Undirected 3-Fault Replacement Path in Nearly Cubic Time

Shucheng Chi, Ran Duan, Benyu Wang, Tianle Xie

To appear in the 52nd International Colloquium on Automata, Languages, and Programming (ICALP '25)

arXiv

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths

Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, Longhui Yin

To appear in Proceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC '25)

arXiv

More Asymmetry Yields Faster Matrix Multiplication

Josh Alman, Ran Duan, Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou

In Proceedings of the 36th ACM-SIAM Symposium on Discrete Algorithms (SODA '25)

arXiv

A Randomized Algorithm for Single-Source Shortest Path on Undirected Real-Weighted Graphs

Ran Duan, Jiayi Mao, Xinkai Shu, Longhui Yin

In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS '23)

arXiv

Faster Matrix Multiplication via Asymmetric Hashing

Ran Duan, Hongxun Wu, Renfei Zhou

In Proceedings of the 64th Annual Symposium on Foundations of Computer Science (FOCS '23)

arXiv

Maintaining Exact Distances under Multiple Edge Failures

Ran Duan, Hanlin Ren

In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC '22)

arXiv

Faster Min-Plus Product for Monotone Instances

Shucheng Chi, Ran Duan, Tianle Xie, Tianyi Zhang

In Proceedings of the 54th Annual ACM Symposium on Theory of Computing (STOC '22)

arXiv

Faster Algorithms for Bounded-Difference Min-Plus Product

Shucheng Chi, Ran Duan, Tianle Xie

In Proceedings of the 33rd ACM-SIAM Symposium on Discrete Algorithms (SODA '22)

arXiv

Near-Optimal Time-Energy Trade-Offs for Deterministic Leader Election

Yi-Jun Chang, Ran Duan, Shunhua Jiang

In the 33rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA '21)

arXiv

Approximate Distance Oracles Subject to Multiple Vertex Failures

Ran Duan, Yong Gu, Hanlin Ren

In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA '21)

arXiv

A Scaling Algorithm for Weighted f-Factors in General Graphs

Ran Duan, Haoqing He, Tianyi Zhang

In the 47th International Colloquium on Automata, Languages, and Programming (ICALP '20)

arXiv

Roundtrip Spanners with (2k-1) Stretch

Ruoxu Cen, Ran Duan, Yong Gu

In the 47th International Colloquium on Automata, Languages, and Programming (ICALP '20)

arXiv

Near-linear Time Algorithms for Approximate Minimum Degree Spanning Trees

Ran Duan, Haoqing He, Tianyi Zhang

In the 14th Latin American Theoretical Informatics Symposium (LATIN '20)

arXiv

Faster Algorithms for All Pairs Non-decreasing Paths Problem

Ran Duan, Ce Jin, Hongxun Wu

In the 46th International Colloquium on Automata, Languages, and Programming (ICALP '19)

arXiv

Dynamic Edge Coloring with Improved Approximation

Ran Duan, Haoqing He, Tianyi Zhang

In Proceedings of the 30th ACM-SIAM Symposium on Discrete Algorithms (SODA '19)

Approximating All-Pair Bounded-Leg Shortest Path and APSP-AF in Truly-Subcubic Time

Ran Duan, Hanlin Ren

In the 45th International Colloquium on Automata, Languages, and Programming (ICALP '18)

Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs

Ran Duan, Kaifeng Lyu, Yuanhang Xie

In the 45th International Colloquium on Automata, Languages, and Programming (ICALP '18)

arXiv version with slightly better bound by Hongxun Wu

Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs

Ran Duan, Yong Gu, Le Zhang

In the 45th International Colloquium on Automata, Languages, and Programming (ICALP '18)

Improved Algorithms for Maintaining DFS Tree in Undirected Graphs

Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang, Tianyi Zhang

In the Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '18)

arXiv

Improved Distance Sensitivity Oracles via Tree Partitioning

Ran Duan, Tianyi Zhang

In the Algorithms and Data Structures Symposium (WADS '17)

arXiv

Faster Worst-Case Update Time for Dynamic Subgraph Connectivity

Ran Duan, Le Zhang

In the Algorithms and Data Structures Symposium (WADS '17)

arXiv

Scaling Algorithms for Weighted Matching in General Graphs

Ran Duan, Seth Pettie, Hsin-Hao Su

In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA '17)

Connectivity Oracles for Graphs Subject to Vertex Failures

Ran Duan, Seth Pettie

In Proceedings of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA '17)

arXiv

An Improved Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market

Ran Duan, Jugal Garg, Kurt Mehlhorn

In Proceedings of the 27th ACM-SIAM Symposium on Discrete Algorithms (SODA '16)

arXiv

Approximation Algorithms for the Gromov Hyperbolicity of Discrete Metric Spaces

Ran Duan

In proceedings of the 11th Latin American Theoretical Informatics Symposium (LATIN '14)

A Combinatorial Polynomial Algorithm for the Linear Arrow-Debreu Market

Ran Duan, Kurt Mehlhorn

In Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP '13)

Breaking the $O(n^{2.5})$ Deterministic Time Barrier for Undirected Unit-Capacity Maximum Flow

Ran Duan

In Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA '13)

A Scaling Algorithm for Maximum Weight Matching in Bipartite Graphs

Ran Duan, Hsin-Hao Su

In Proceedings of the 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA '12)

Approximating Maximum Weight Matching in Near-linear Time

Ran Duan, Seth Pettie

In Proceedings of the 51st IEEE Symposium on Foundations of Computer Science (FOCS '10)

New Data Structures for Subgraph Connectivity

Ran Duan

In Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP '10)

Connectivity Oracles for Failure Prone Graphs

Ran Duan, Seth Pettie

In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC '10)

Dual-Failure Distance and Connectivity Oracles

Ran Duan, Seth Pettie

In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09)

Fast Algorithms for (Max,Min)-Matrix Multiplication and Bottleneck Shortest Paths

Ran Duan, Seth Pettie

In Proceedings of the 20th ACM-SIAM Symposium on Discrete Algorithms (SODA '09)

Bounded-leg Distance and Reachability Oracles

Ran Duan, Seth Pettie

In Proceedings of the 19th ACM-SIAM Symposium on Discrete Algorithms (SODA '08)

2011 德国洪堡奖学金