Ran Duan
Assistant Professor
Institute for Interdisciplinary Information Sciences

Address: FIT 1-208, Tsinghua University, 100084, Beijing, China


 

Education Background

 


2002.9~2006.7 B.E. Computer Science and Technology, Tsinghua University, Beijing
2006.8~2011.8 Ph.D. Computer Science and Engineering, University of Michigan, Ann Arbor
2011.9~2014.8 Postdoctoral Researcher, Max-Planck-Institut für Informatik, Saarbrücken



Research Interests


Graph Algorithms, Data Structures, Approximate and Randomized Algorithms, Algorithmic Game Theory



Awards


2011 Humboldt fellowship


Teaching


IIIS, Tsinghua University:

Theory of Computation (Undergraduate level), Spring 2015, Spring 2016, Spring 2017, Spring 2018

Design and Analysis of Algorithms (Graduate level), Fall 2015, Fall 2016, Fall 2017

Theory and Practice of Computer Science (Undergraduate level), Summer 2016, Summer 2017

 

Universität des Saarlandes:

Summer 2012, Advanced Graph Algorithms (Graduate level), co-lecturer with Jens M. Schmidt and  Magnus Wahlström

 

Manuscripts/In Submission


Near-linear Time Algorithms for Approximate Minimum Degree Spanning Trees
Ran Duan, Haoqing He, Tianyi Zhang
In Submission>
arXiv

 

 

 

Journal Articles


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

 

 

 

Conference Papers


Dynamic Edge Coloring with Improved Approximation
Ran Duan, Haoqing He, Tianyi Zhang
In Proceedings of the 26th 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 24th ACM-SIAM Symposium on Discrete Algorithms (SODA '17)


Connectivity Oracles for Graphs Subject to Vertex Failures
Ran Duan, Seth Pettie
In Proceedings of the 24th 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 24th 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)


 

 

 

Talks and Slides