Arrow Research search

Author name cluster

Ran Duan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

23 papers
2 author rows

Possible papers

23

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.

Details

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.

Details DOI

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.

Details

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.

Details

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.

PDF Details DOI

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 ).

Details

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 ).

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details

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.

Details