Ran Duan

IROS Conference 2025 Conference Paper

3D Gaussian Splatting for Fine-Detailed Surface Reconstruction in Large-Scale Scene

• Shihan Chen
• Zhaojin Li
• Zeyu Chen
• Qingsong Yan
• Gaoyang Shen
• Ran Duan

Recent developments in 3D Gaussian Splatting have made significant advances in surface reconstruction. However, scaling these methods to large-scale scenes remains challenging due to high computational demands and the complex dynamic appearances typical of outdoor environments. These challenges hinder the application in aerial surveying and autonomous driving. This paper proposes a novel solution to reconstruct large-scale surfaces with fine details, supervised by full-sized images. Firstly, we introduce a coarse-to-fine strategy to reconstruct a coarse model efficiently, followed by adaptive scene partitioning and sub-scene refining from image segments. Additionally, we integrate a decoupling appearance model to capture global appearance variations and a transient mask model to mitigate interference from moving objects. Finally, we expand the multi-view constraint and introduce a single-view regularization for texture-less areas. Our experiments were conducted on the publicly available dataset GauU-Scene V2, which was captured using unmanned aerial vehicles. To the best of our knowledge, our method outperforms existing NeRF-based and Gaussian-based methods, achieving high-fidelity visual results and accurate surface from full-size image optimization. Open-source code will be available on GitHub.

JBHI Journal 2025 Journal Article

Boosting Few-Shot Semantic Segmentation of 3D Medical Images via Collaborative Slice Alignment

• Ran Duan
• Jialun Pei
• Zhiwei Wang
• Ruiheng Zhang
• Qiang Li
• Pheng-Ann Heng

Few-shot semantic segmentation (FSS) of 3D medical images requires finding a 2D slice from the labeled volume as support to ‘query’ slices of the unlabeled one. Accurately determining support slices is crucial for learning representative prototypical features, thereby enhancing segmentation accuracy. The existing methods typically resort to the true position of the query target to align the query with support slices or simply exploit one key support slice to segment all query slices, which inevitably results in poor practicality and mis-segmentation. In this regard, we seek a practical and efficient solution by proposing a novel Collaborative Slice Alignment (CSA) module, which densely assigns each query slice its own fittest support without knowing the target prior. Concretely, our CSA first estimates the confidence scores of slices from the sorting task to implicitly reflect their physical location in the human body. The estimated scores are considered as spatial references for aligning support slices and query slices so that each matching pair shares the most similar image contents. Moreover, the self-learnable ranking objective allows CSA to transfer internal knowledge into both support and query features to further boost the FSS performance. Additionally, we introduce an Information Reconciliation (InRe) module to mitigate the inconsistent feature distribution caused by the individual differences between support and query images. Experimental results demonstrate that the combination of CSA and InRe achieves an average Dice score improvement of at least 8. 61% across three datasets, consistently outperforming other state-of-the-art methods.

EAAI Journal 2025 Journal Article

Heterogeneous graph contrastive learning-based transductive health condition assessment of Francis turbine unit

• Fengyuan Zhang
• Jie Liu
• Yujie Liu
• Yuxin Li
• Ran Duan
• Zhidi Chen
• Xingxing Jiang

To assess the Francis turbine unit's (FTU) degradation status from the onsite data without state labeling, a series of health benchmark model (HBM) driven health condition assessment (HCA) methods have been proposed. However, some limitation still exists, including: 1) Multiple similar HBMs are repeatedly constructed and trained to process multiple heterogeneous monitoring signals, however, there is a lack of a unified model that can handle the full task flow directly. 2) Simple linear methods are used to fuse multiple heterogeneous signals to construct performance degradation indexes (PDIs), ignoring temporal changes in the relationships within the signals and resulting in inadequate unit state representation. In this paper, a heterogeneous graph contrastive learning-based transductive health condition assessment of FTU considering multi-source monitoring signals is proposed. First, multi-source heterogeneous signals are converted into a series of heterogeneous signal graphs via the designed similarity-based edge-connection function considering the temporal representation differences. Then, an innovative graph-level heterogenous signal fusion method is proposed to represent unit conditions completely. By concatenating adjacency matrices of the heterogeneous signal graphs, multiple edge connections within the assessment period data are fused, obtaining a unique interactive graph with balanced and extended edge connections. Further, GCL-driven graph representator model is used to maximize the differences between the healthy and degraded interactive graph (IGs), and then the distances between the model readout vectors of the above two graphs is calculated as IPDIs, considering the signal correlations influenced by unit state changes. Verification experiments show that the proposed transductive HCA method effectively evaluates FTU's degradation without state labeling.

SODA Conference 2025 Conference Paper

More Asymmetry Yields Faster Matrix Multiplication

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

FOCS Conference 2023 Conference Paper

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

• Ran Duan
• Jiayi Mao
• Xinkai Shu
• Longhui Yin

In undirected graphs with real non-negative weights, we give a new randomized algorithm for the single-source shortest path (SSSP) problem with running time $O(m \sqrt{\log n \cdot \log \log n})$ in the comparison-addition model. This is the first algorithm to break the $O(m+n \log n)$ time bound for real-weighted sparse graphs by Dijkstra’s algorithm with Fibonacci heaps. Previous undirected nonnegative SSSP algorithms give time bound of $O(m \alpha(m, n)+ \min \{n \log n, n \log \log r\})$ in comparison-addition model, where $\alpha$ is the inverse-Ackermann function and r is the ratio of the maximum-to-minimum edge weight [Pettie & Ramachandran 2005], and linear time for integer edge weights in RAM model [Thorup 1999]. Note that there is a proposed complexity lower bound of $\Omega(m+\min \{n \log n, n \log \log r\})$ for hierarchy-based algorithms for undirected real-weighted SSSP [Pettie & Ramachandran 2005], but our algorithm does not obey the properties required for that lower bound. As a non-hierarchybased approach, our algorithm shows great advantage with much simpler structure, and is much easier to implement.

FOCS Conference 2023 Conference Paper

Faster Matrix Multiplication via Asymmetric Hashing

• Ran Duan
• Hongxun Wu
• Renfei Zhou

Fast matrix multiplication is one of the most fundamental problems in algorithm research. The exponent of the optimal time complexity of matrix multiplication is usually denoted by $\omega$. This paper discusses new ideas for improving the laser method for fast matrix multiplication. We observe that the analysis of higher powers of the Coppersmith-Winograd tensor [Coppersmith & Winograd 1990] incurs a “combination loss”, and we partially compensate for it using an asymmetric version of CW’s hashing method. By analyzing the eighth power of the CW tensor, we give a new bound of $\omega/\lt2. 371866$, which improves the previous best bound of $\omega/\lt2. 372860$ [Alman & Vassilevska Williams 2020]. Our result breaks the lower bound of 2. 3725 in [Ambainis, Filmus & Le Gall 2015] because of the new method for analyzing component (constituent) tensors.

AAAI Conference 2023 Conference Paper

Robust One-Shot Segmentation of Brain Tissues via Image-Aligned Style Transformation

• Jinxin Lv
• Xiaoyu Zeng
• Sheng Wang
• Ran Duan
• Zhiwei Wang
• Qiang Li

One-shot segmentation of brain tissues is typically a dual-model iterative learning: a registration model (reg-model) warps a carefully-labeled atlas onto unlabeled images to initialize their pseudo masks for training a segmentation model (seg-model); the seg-model revises the pseudo masks to enhance the reg-model for a better warping in the next iteration. However, there is a key weakness in such dual-model iteration that the spatial misalignment inevitably caused by the reg-model could misguide the seg-model, which makes it converge on an inferior segmentation performance eventually. In this paper, we propose a novel image-aligned style transformation to reinforce the dual-model iterative learning for robust one-shot segmentation of brain tissues. Specifically, we first utilize the reg-model to warp the atlas onto an unlabeled image, and then employ the Fourier-based amplitude exchange with perturbation to transplant the style of the unlabeled image into the aligned atlas. This allows the subsequent seg-model to learn on the aligned and style-transferred copies of the atlas instead of unlabeled images, which naturally guarantees the correct spatial correspondence of an image-mask training pair, without sacrificing the diversity of intensity patterns carried by the unlabeled images. Furthermore, we introduce a feature-aware content consistency in addition to the image-level similarity to constrain the reg-model for a promising initialization, which avoids the collapse of image-aligned style transformation in the first iteration. Experimental results on two public datasets demonstrate 1) a competitive segmentation performance of our method compared to the fully-supervised method, and 2) a superior performance over other state-of-the-art with an increase of average Dice by up to 4.67%. The source code is available at: https://github.com/JinxLv/One-shot-segmentation-via-IST.

SODA Conference 2022 Conference Paper

Faster Algorithms for Bounded-Difference Min-Plus Product

• Shucheng Chi
• Ran Duan
• Tianle Xie

Min-plus product of two n × n matrices is a fundamental problem in algorithm research. It is known to be equivalent to APSP, and in general it has no truly subcubic algorithms. In this paper, we focus on the min-plus product on a special class of matrices, δ -bounded-difference matrices, in which the difference between any two adjacent entries is bounded by δ = O (1). Our algorithm runs in randomized time O ( n 2. 779 ) by the fast rectangular matrix multiplication algorithm [Le Gall & Urrutia 18], better than Õ ( n 2+ ω/ 3 ) = O ( n 2. 791 ) ( ω < 2. 373 [Alman & V. V. Williams 20]). This improves the previous result of Õ ( n 2. 824 ) [Bringmann et al. 16]. When ω = 2 in the ideal case, our complexity is Õ ( n 2+2/3 ), improving Bringmann et al. 's result of Õ ( n 2. 755 ).

STOC Conference 2022 Conference Paper

Faster min-plus product for monotone instances

• Shucheng Chi
• Ran Duan
• Tianle Xie
• Tianyi Zhang 0008

In this paper, we show that the time complexity of monotone min-plus product of two n × n matrices is Õ( n (3+ω)/2 )=Õ( n 2.687 ), where ω < 2.373 is the fast matrix multiplication exponent [Alman and Vassilevska Williams 2021]. That is, when A is an arbitrary integer matrix and B is either row-monotone or column-monotone with integer elements bounded by O ( n ), computing the min-plus product C where C i , j =min k { A i , k + B k , j } takes Õ( n (3+ω)/2 ) time, which greatly improves the previous time bound of Õ( n (12+ω)/5 )=Õ( n 2.875 ) [Gu, Polak, Vassilevska Williams and Xu 2021]. Then by simple reductions, this means the case that A is arbitrary and the columns or rows of B are bounded-difference can also be solved in Õ( n (3+ω)/2 ) time, whose previous result gives time complexity of Õ( n 2.922 ) [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. So the case that both of A and B are bounded-difference also has Õ( n (3+ω)/2 ) time algorithm, whose previous results give time complexities of Õ( n 2.824 ) [Bringmann, Grandoni, Saha and Vassilevska Williams 2016] and Õ( n 2.779 ) [Chi, Duan and Xie 2022]. Many problems are reducible to these problems, such as language edit distance, RNA-folding, scored parsing problem on BD grammars [Bringmann, Grandoni, Saha and Vassilevska Williams 2016]. Thus, their complexities are all improved. Finally, we also consider the problem of min-plus convolution between two integral sequences which are monotone and bounded by O ( n ), and achieve a running time upper bound of Õ( n 1.5 ). Previously, this task requires running time Õ( n (9+√177)/12 ) = O ( n 1.859 ) [Chan and Lewenstein 2015].

STOC Conference 2022 Conference Paper

Maintaining exact distances under multiple edge failures

• Ran Duan
• Hanlin Ren

We present the first compact distance oracle that tolerates multiple failures and maintains *exact* distances. Given an undirected weighted graph G = ( V , E ) and an arbitrarily large constant d , we construct an oracle that given vertices u , v ∈ V and a set of d edge failures D , outputs the *exact* distance between u and v in G − D (that is, G with edges in D removed). Our oracle has space complexity O ( d n 4 ) and query time d O ( d ) . Previously, there were compact *approximate* distance oracles under multiple failures [Chechik, Cohen, Fiat, and Kaplan, SODA’17; Duan, Gu, and Ren, SODA’21], but the best exact distance oracles under d failures require essentially Ω( n d ) space [Duan and Pettie, SODA’09]. Our distance oracle seems to require n Ω( d ) time to preprocess; we leave it as an open question to improve this preprocessing time.

SODA Conference 2021 Conference Paper

Approximate Distance Oracles Subject to Multiple Vertex Failures

• Ran Duan
• Yong Gu
• Hanlin Ren

Given an undirected graph G = ( V, E ) of n vertices and m edges with weights in [1, W ], we construct vertex sensitive distance oracles (VSDO), which are data structures that preprocess the graph, and answer the following kind of queries: Given a source vertex u, a target vertex v, and a batch of d failed vertices D, output (an approximation of) the distance between u and v in G – D (that is, the graph G with vertices in D removed). An oracle has stretch α if it always holds that, where δ G–D ( u, v ) is the actual distance between u and v in G – D, and is the distance reported by the oracle. In this paper we construct efficient VSDOs for any number d of failures. For any constant c ≥ 1, we propose two oracles: The first oracle has size n 2+1/ c (log n/∊ ) O ( d ) · log W, answers a query in poly(log n, d c, log log W, ∊ –1 ) time, and has stretch 1 + ∊, for any constant ∊ > 0. The second oracle has size n 2+1/ c poly (log( nW ), d ), answers a query in poly (log n, d c, log log W ) time, and has stretch poly (log n, d ). Both of these oracles can be preprocessed in time polynomial in their space complexity. These results are the first approximate distance oracles of poly-logarithmic query time for any constant number of vertex failures in general undirected graphs. Previously there are (1 + ∊)-approximate d-edge sensitive distance oracles [Chechik et al. 2017] answering distance queries when d edges fail, which have size O ( n 2 (log n/∊ ) d · d log W ) and query time poly (log n, d, log log W ).

SODA Conference 2019 Conference Paper

Dynamic Edge Coloring with Improved Approximation

• Ran Duan
• Haoqing He
• Tianyi Zhang 0008

Given an undirected simple graph G = ( V, E ) that undergoes edge insertions and deletions, we wish to efficiently maintain an edge coloring with only a few colors. The previous best dynamic algorithm by [3] could deterministically maintain a valid edge coloring using 2Δ – 1 colors with O (log Δ) update time, where Δ stands for the current maximum vertex degree of graph G. In this paper, we first propose a new static (1 + ∊ )Δ edge coloring algorithm that runs in near-linear time. Based on this static algorithm, we show that there is a randomized dynamic algorithm for this problem that only uses (1 + ∊ )Δ colors with O (log 8 n / ∊ 4 ) amortized update time when Δ ≥ Ω(log 2 n / ∊ 2 ), where ∊ > 0 is an arbitrarily small constant.

SODA Conference 2017 Conference Paper

Connectivity Oracles for Graphs Subject to Vertex Failures

• Ran Duan
• Seth Pettie

We introduce new data structures for answering connectivity queries in graphs subject to batched vertex failures. Our deterministic structure processes a batch of d ≤ d * failed vertices in Õ ( d 3 ) time and thereafter answers connectivity queries in Õ(d) time. It occupies space Õ ( d * m log n ). We develop a randomized Monte Carlo version of our data structure with update time Õ ( d 2 ), query time Õ ( d ), and space Õ ( m ) for any d*. This is the first connectivity oracle for general graphs that can efficiently deal with an unbounded number of vertex failures. Our data structures are based on a new decomposition theorem for an undirected graph G = ( V, E ), which is of independent interest. It states that for any terminal set U ⊆ V we can remove a set B of | U |/( s — 2) vertices such that the remaining graph contains a Steiner forest for U - B with maximum degree s.

SODA Conference 2017 Conference Paper

Scaling Algorithms for Weighted Matching in General Graphs

• Ran Duan
• Seth Pettie
• Hsin-Hao Su

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in time, per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs [29, 18]. Here m, n, and n bound the number of edges, vertices, and magnitude of any integer edge weight. Our result improves on a 25-year old algorithm of Gabow and Tarjan, which runs in time.

EAAI Journal 2017 Journal Article

Tracking–recommendation–detection: A novel online target modeling for visual tracking

• Ran Duan
• Changhong Fu
• Erdal Kayacan

In this paper, we propose a novel object tracking algorithm which combines a tracking-by-detection approach with a recommender system. The proposed algorithm consists of two steps: (1) to match detected features with a three-layer feature dictionary, i. e. , target appearance model, which is initially built on the first frame and being adaptive frame-by-frame; (2) to add detected features into the aforementioned dictionary and use a recommender system to optimize the dictionary simultaneously. Among the two steps, while the former determines a new location for the target, the latter updates the target appearance model. Extensive experiments, which are done on 20 benchmark video sequences, demonstrate that the tracking results for the proposed novel method outperforms the state-of-the-art trackers both in terms of accuracy and robustness.

SODA Conference 2016 Conference Paper

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

• Ran Duan
• Jugal Garg
• Kurt Mehlhorn

We present an improved combinatorial algorithm for the computation of equilibrium prices in the linear Arrow-Debreu model. For a market with n agents and integral utilities bounded by U, the algorithm runs in O ( n 7 log 3 ( nU )) time. This improves upon the previously best algorithm of Ye by a factor of. The algorithm refines the algorithm described by Duan and Mehlhorn and improves it by a factor of. The improvement comes from a better understanding of the iterative price adjustment process, the improved balanced flow computation for nondegenerate instances, and a novel perturbation technique for achieving nondegeneracy.

I&C Journal 2015 Journal Article

A combinatorial polynomial algorithm for the linear Arrow–Debreu market

• Ran Duan
• Kurt Mehlhorn

We present the first combinatorial polynomial time algorithm for computing the equilibrium of the Arrow–Debreu market model with linear utilities. Our algorithm views the allocation of money as flows and iteratively improves the balanced flow as in [11] for Fisher's model. We develop new methods to carefully deal with the flows and surpluses during price adjustments. Our algorithm performs O ( n 6 log ⁡ ( n U ) ) maximum flow computations, where n is the number of agents and U is the maximum integer utility. The flows have to be presented as numbers of bitlength O ( n log ⁡ ( n U ) ) to guarantee an exact solution. Previously, [22, 29] have given polynomial time algorithms for this problem, which are based on solving convex programs using the ellipsoid algorithm and the interior-point method, respectively.

SODA Conference 2013 Conference Paper

Breaking the O(n 2. 5 ) Deterministic Time Barrier for Undirected Unit-Capacity Maximum Flow

• Ran Duan

SODA Conference 2012 Conference Paper

A scaling algorithm for maximum weight matching in bipartite graphs

• Ran Duan
• Hsin-Hao Su

FOCS Conference 2010 Conference Paper

Approximating Maximum Weight Matching in Near-Linear Time

• Ran Duan
• Seth Pettie

Given a weighted graph, the maximum weight matching problem (MWM) is to find a set of vertex-disjoint edges with maximum weight. In the 1960s Edmonds showed that MWMs can be found in polynomial time. At present the fastest MWM algorithm, due to Gabow and Tarjan, runs in Õ(m√n) time, where m and n are the number of edges and vertices in the graph. Surprisingly, restricted versions of the problem, such as computing (1 - ϵ)-approximate MWMs or finding maximum cardinality matchings, are not known to be much easier (on sparse graphs). The best algorithms for these problems also run in Õ(m√n) time. In this paper we present the first near-linear time algorithm for computing (1 - e)-approximate MWMs. Specifically, given an arbitrary real-weighted graph and ϵ > 0, our algorithm computes such a matching in O(mϵ -2 log 3 n) time. The previous best approximate MWM algorithm with comparable running time could only guarantee a (2/3 - ϵ)-approximate solution. In addition, we present a faster algorithm, running in O(m log n log ϵ -1 ) time, that computes a (3/4 - ϵ)-approximate MWM.

STOC Conference 2010 Conference Paper

Connectivity oracles for failure prone graphs

• Ran Duan
• Seth Pettie

Dynamic graph connectivity algorithms have been studied for many years, but typically in the most general possible setting, where the graph can evolve in completely arbitrary ways. In this paper we consider a dynamic subgraph model. We assume there is some fixed, underlying graph that can be preprocessed ahead of time. The graph is subject only to vertices and edges flipping "off" (failing) and "on" (recovering), where queries naturally apply to the subgraph on edges/vertices currently flipped on. This model fits most real world scenarios, where the topology of the graph in question (say a router network or road network) is constantly evolving due to temporary failures but never deviates too far from the ideal failure-free state.

SODA Conference 2009 Conference Paper

Dual-failure distance and connectivity oracles

• Ran Duan
• Seth Pettie

Spontaneous failure is an unavoidable aspect of all networks, particularly those with a physical basis such as communications networks or road networks. Whether due to malicious coordinated attacks or other causes, failures temporarily change the topology of the network and, as a consequence, its connectivity and distance metric. In this paper we look at the problem of efficiently answering connectivity, distance, and shortest route queries in the presence of two node or link failures. Our data structure uses Õ ( n 2 ) space and answers queries in Õ (1) time, which is within a polylogarithmic factor of optimal and nearly matches the single-failure distance oracles of Demestrescu et al. It may yet be possible to find distance/connectivity oracles capable of handling any fixed number of failures. However, the sheer complexity of our algorithm suggests that moving beyond dual-failures will require a fundamentally different approach to the problem.

SODA Conference 2009 Conference Paper

Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths

• Ran Duan
• Seth Pettie

Given a directed graph with a capacity on each edge, the all-pairs bottleneck paths (APBP) problem is to determine, for all vertices s and t, the maximum flow that can be routed from s to t. For dense graphs this problem is equivalent to that of computing the (max, min)-transitive closure of a real-valued matrix. In this paper, we give a (max, min)-matrix multiplication algorithm running in time O ( n (3+ω)/2 ) ≤ O ( n 2. 688 ), where ω is the exponent of binary matrix multiplication. Our algorithm improves on a recent O ( n 2+ω/3 ) ≤ O ( n 2. 792 )-time algorithm of Vassilevska, Williams, and Yuster. Although our algorithm is slower than the best APBP algorithm on vertex capacitated graphs, running in O ( n 2. 575 ) time, it is just as efficient as the best algorithm for computing the dominance product, a problem closely related to (max, min)-matrix multiplication. Our techniques can be extended to give subcubic algorithms for related bottleneck problems. The all-pairs bottleneck shortest paths problem (APBSP) asks for the maximum flow that can be routed along a shortest path. We give an APBSP algorithm for edge-capacitated graphs running in O ( n (3+ω)/2 ) time and a slightly faster O ( n 2. 657 )-time algorithm for vertex-capactitated graphs. The second algorithm significantly improves on an O ( n 2. 859 )-time APBSP algorithm of Shapira, Yuster, and Zwick. Our APBSP algorithms make use of new hybrid products we call the distance-max-min product and dominance-distance product.

SODA Conference 2008 Conference Paper

Bounded-leg distance and reachability oracles

• Ran Duan
• Seth Pettie