Author name cluster

Limei Liu

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.

6 papers

1 author row

AAAI Conference 2026 Conference Paper

A More Efficient Reduction from Outlier-Aware to Outlier-Free k-Median

Zhen Zhang
Han Peng
Limei Liu
Junyu Huang
Xiaolong Li
Qilong Feng

Given a non-negative integer \ell, the k-median with outliers problem extends the standard k-median problem by allowing the removal of up to \ell points and minimizing the clustering cost over the remaining ones. Algorithmic development in this setting remains an active area of research due to its relevance in processing noisy data. In this paper, we present a sampling-based reduction from the k-median with outliers problem to its outlier-free counterpart. The reduction incurs a multiplicative overhead of (kℓ⁻¹ + ε⁻¹)^O(ℓ) in the running time: it yields (kℓ⁻¹ + ε⁻¹)^O(ℓ) outlier-free instances, a solution to one of which can be directly transformed into a solution to the original instance with an arbitrarily small loss in the approximation ratio. This improves upon the previously known reduction with an overhead of ((k + ℓ)ε⁻¹)^O(ℓ). As applications, we obtain faster fixed-parameter tractable (FPT) algorithms with tight approximation guarantees for the k-median with outliers problem under various metric spaces. Furthermore, our approach naturally generalizes to constrained variants of the problem where additional constraints are imposed on the cluster sizes, and yields similar improvements in their FPT approximations.

PDF Details DOI

EAAI Journal 2025 Journal Article

A two-stage point elimination with salient fusion features for point cloud registration

Baifan Chen
Zeshun Zhou
Limei Liu
Lingli Yu
Xushi Li

Point cloud registration aims to estimate the rigid transformation between two point clouds, which has a crucial role in robotics and computer vision. Low-overlap point cloud registration is a challenging task: (1) Existing methods primarily extract geometric features for registration. Methods only relying on local geometric features may fail under low-overlap cases, especially when dealing with point clouds containing similar or symmetric structures. (2) Most current methods struggle to accurately estimate the overlapping regions, often resulting in the inclusion of numerous outliers that cause registration failures. To address these issues, we propose a two-stage point elimination with salient fusion features registration network (PE2-SFFNet). The PE2-SFFNet is composed of Feature Extraction and Fusion (FEF) module and two-stage point elimination module (PE2). The FEF module leverages global context to guide matching and multi-scale local geometric structures to distinguish fine details in point clouds. To mitigate the impact of outliers, we introduce the PE2 module. In the first stage, a Feature Similarity-guided Overlap Estimation Network (FSOEN) is used to identify salient points and salient fusion features (SFF), eliminating most of the negative impact caused by outliers. In the second stage, a Weight Assignment Network (WAN) is applied to reduce the weight of mismatched point pairs, further improving the algorithm’s accuracy. We conduct experiments on both synthetic and real-world datasets. The results demonstrate that our method outperforms other partial registration algorithms, achieving superior registration performance.

Details DOI

TCS Journal 2025 Journal Article

Clustering under a knapsack constraint: Parameterized approximation for the knapsack median problem

Zhen Zhang
Zhuohang Gao
Limei Liu
Yao Liu
Jie Chen
Qilong Feng

The Knapsack Median problem, defined over a set of clients and facilities in a metric space, seeks to open a subset of facilities and connect each client to an opened facility, with the goal of minimizing the sum of client-connection costs while keeping the sum of facility-opening costs within a specified budget. Solving this problem exactly in FPT time, parameterized by the maximum number of opened facilities (denoted by k), is unlikely due to its W[2]-hardness. Thus, we focus on parameterized approximation algorithms for the problem. We give a sampling-based method that reduces the solution search space, which yields a ( 3 + ε ) -approximation algorithm running in ( k ε − 1 ) O ( k ) n O ( 1 ) time in general metric spaces and a ( 1 + ε ) -approximation algorithm with similar running time in d-dimensional Euclidean space.

Details DOI

NeurIPS Conference 2024 Conference Paper

Parameterized Approximation Schemes for Fair-Range Clustering

Zhen Zhang
Xiaohong Chen
Limei Liu
Jie Chen
Junyu Huang
Qilong Feng

Fair-range clustering extends classical clustering formulations by associating each data point with one or more demographic labels. It imposes lower and upper bound constraints on the number of facilities opened for each label, ensuring fair representation of all demographic groups by the selected facilities. In this paper we focus on the fair-range $k$-median and $k$-means problems in Euclidean spaces. We give $(1+\varepsilon)$-approximation algorithms with fixed-parameter tractable running times for both problems, parameterized by the numbers of opened facilities and demographic labels. For Euclidean metrics, these are the first parameterized approximation schemes for the problems, improving upon the previously known $O(1)$-approximation ratios given by Thejaswi et al. (KDD 2022).

PDF Details DOI

EAAI Journal 2024 Journal Article

The extended weighted t-norms-based linear hybrid aggregation function and its application for aggregating improved basic uncertain linguistic information

Yi Yang
Mengqi Jie
Yuhan Zhao
Limei Liu
Junfeng Yang
Jie Chen

In recent decades, the Archimedean triangular norm (t-norm) and Archimedean triangular conorm (t-conorm) have been fundamental theories in the design and construction of information aggregation functions. The application of weighted Archimedean t-norm/t-conorm-based aggregation functions has been widely extended to uncertain information environments, such as fuzzy sets and linguistic term sets. However, these functions are susceptible to aggregation failure when dealing with information groups that contain extreme values, leading to unreasonable aggregation results. This paper aims to address the issue of aggregation failure by developing an extended Archimedean t-norm/t-conorm-based linear hybrid aggregation framework. Firstly, the extended weighted Archimedean t-norms and t-conorms that are suitable for processing linguistic term sets are proposed. Furthermore, an aggregation contribution function is introduced to evaluate the impact of both extreme and normal values on aggregated outcomes. This function also facilitates the identification of deficiencies within existing weighted Archimedean t-norm/t-conorm-based aggregation functions. Secondly, building upon the expanded Archimedean t-norm/t-conorm as the foundational framework, a linear weighted hybrid operator is developed by employing an extreme value identification function as guidance. The rationality of this operator is validated through the utilization of previously defined aggregation contribution function. Subsequently, to consolidate improved basic uncertain linguistic information (IBULI) pairs, the proposed hybrid operator is employed for constructing an IBULI-aggregation function. Finally, a product ranking method is developed by integrating the proposed operator and incorporating a user credibility calculation-based approach for converting ratings to IBULIs. The efficacy and rationality of the proposed approach is substantiated through a case study and comparative analysis of car ranking application.

Details DOI

AAAI Conference 2024 Conference Paper

Towards a Theoretical Understanding of Why Local Search Works for Clustering with Fair-Center Representation

Zhen Zhang
Junfeng Yang
Limei Liu
Xuesong Xu
Guozhen Rong
Qilong Feng

The representative k-median problem generalizes the classical clustering formulations in that it partitions the data points into several disjoint demographic groups and poses a lower-bound constraint on the number of opened facilities from each group, such that all the groups are fairly represented by the opened facilities. Due to its simplicity, the local-search heuristic that optimizes an initial solution by iteratively swapping at most a constant number of closed facilities for the same number of opened ones (denoted by the O(1)-swap heuristic) has been frequently used in the representative k-median problem. Unfortunately, despite its good performance exhibited in experiments, whether the O(1)-swap heuristic has provable approximation guarantees for the case where the number of groups is more than 2 remains an open question for a long time. As an answer to this question, we show that the O(1)-swap heuristic (1) is guaranteed to yield a constant-factor approximation solution if the number of groups is a constant, and (2) has an unbounded approximation ratio otherwise. Our main technical contribution is a new approach for theoretically analyzing local-search heuristics, which derives the approximation ratio of the O(1)-swap heuristic via linearly combining the increased clustering costs induced by a set of hierarchically organized swaps.

PDF Details DOI