清华大学交叉信息研究院

段然
职务: 助理教授
Email:
地址: 清华大学FIT楼1-208


 

Education Background


2002.9~2006.7 本科 清华大学计算机科学与技术系
2006.8~2011.8 博士 (美国)密歇根大学计算机系
2011.9~2014.8 博士后研究员 (德国)马克斯普朗克信息学研究所


Research Interests


图论算法、数据结构、近似和随机算法、算法博弈论

 

Awards


2011 德国洪堡奖学金
2015 青年千人计划


Teaching


清华大学交叉信息研究院:

2017夏,现代信息技术理论与实践(本科生)

2017春,计算理论(本科生)

2016秋,算法设计与分析(研究生)

2016夏,现代信息技术理论与实践(本科生)

2016春,计算理论(本科生)

2015秋,算法设计与分析(研究生)

2015春,计算理论(本科生)

 

萨尔大学(德国):

2012夏,高等图论算法(研究生),与Jens M. Schmidt 和 Magnus Wahlström 合讲

 

Manuscripts/In Submission


Improved Algorithms for Maintaining DFS Tree in Undirected Graphs
Lijie Chen, Ran Duan, Ruosong Wang, Hanrui Zhang
In Submission

arXiv

 

 

Journal Articles


Linear-Time Approximation for Maximum Weight Matching
Ran Duan, Seth Pettie
Journal of the ACM, 61(1):1-23, 2014

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

 

Conference Papers


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)

arXiv

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