Author name cluster

Longkun Guo

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.

14 papers

1 author row

AAAI Conference 2026 Conference Paper

Approximation Algorithm for Constrained k-Center Clustering: A Local Search Approach

Chaoqi Jia
Longkun Guo
Kewen Liao
Zhigang Lu
Chao Chen
Jason Xue

Clustering is a long-standing research problem and a fundamental tool in AI and data analysis. The traditional k-center problem, known as a fundamental theoretical challenge in clustering, has a best possible approximation ratio of 2, and any improvement to a ratio of 2 - ε would imply P = NP. In this work, we study the constrained k-center clustering problem, where instance-level cannot-link (CL) and must-link (ML) constraints are incorporated as background knowledge. Although general CL constraints significantly increase the hardness of approximation, previous work has shown that disjoint CL sets permit constant-factor approximations. However, whether local search can achieve such a guarantee in this setting remains an open question. To this end, we propose a novel local search framework based on a transformation to a dominating matching set problem, achieving the best possible approximation ratio of 2. The experimental results on both real-world and synthetic datasets demonstrate that our algorithm outperforms baselines in solution quality.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Improved Streaming Algorithm for Fair k-Center Clustering

Longkun Guo
Zeyu Lin
Chaoqi Jia
Chao Chen

Many real-world applications call for incorporating fairness constraints into the k-center clustering problem, where the dataset is partitioned into m demographic groups, each with a specified upper bound on the number of centers to ensure fairness. Focusing on big data scenarios, this paper addresses the problem in a streaming setting, where data points arrive sequentially in a continuous stream. Leveraging a structure called the λ-independent center set, we propose a one-pass streaming algorithm that first computes a reserved set of points during the streaming process. In the post-streaming process, we then select centers from the reserved point set by analyzing three possible cases and transforming the most complex one into a specially constrained vertex-cover problem on an auxiliary graph. Our algorithm achieves an approximation ratio of 5 +? and memory complexity O(k log?), where? is the aspect ratio and? > 0 is any small constant. Furthermore, we extend our approach to semi-structured data streams, where data points arrive in groups. In this setting, we present a (3 +?)-approximation algorithm for m = 2, which can be readily adapted to solve the offline fair k-center problem, achieving an approximation ratio of 3 that matches the current state of the art. Lastly, we conduct extensive experiments to evaluate the performance of our approaches, demonstrating that they outperform existing baselines in both clustering cost and runtime efficiency.

PDF Details DOI

AAAI Conference 2026 Conference Paper

Optimized Algorithms for Text Clustering with LLM-Generated Constraints

Chaoqi Jia
Weihong Wu
Longkun Guo
Zhigang Lu
Chao Chen
Kok-Leong Ong

Clustering is a fundamental tool that has garnered significant interest across a wide range of applications including text analysis. To improve clustering accuracy, many researchers have proposed incorporating background knowledge, typically in the form of must‑link and cannot‑link constraints, to guide the clustering process. With the recent advent of large language models (LLMs), there is growing interest in improving clustering quality through LLM-based automatic constraint generation. In this paper, we propose a novel constraint‑generation approach that reduces resource consumption by generating constraint sets rather than using traditional pairwise constraints. This improves both query efficiency and constraint accuracy compared to state‑of‑the‑art methods. We further introduce a constrained clustering algorithm tailored to the characteristics of LLM-generated constraints. Our method incorporates a confidence threshold and a penalty mechanism to address potentially inaccurate constraints. We evaluate our approach on five text datasets, considering both the cost of constraint generation and overall clustering performance. The results show that our method achieves clustering accuracy comparable to the state-of-the-art algorithms while reducing the number of LLM queries by more than 20 times.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Curriculum-Enhanced Residual Soft An-Isotropic Normalization for Over-Smoothness in Deep GNNs

Jin Li
Qirong Zhang
Shuling Xu
Xinlong Chen
Longkun Guo
Yang-Geng Fu

Despite Graph neural networks' significant performance gain over many classic techniques in various graph-related downstream tasks, their successes are restricted in shallow models due to over-smoothness and the difficulties of optimizations among many other issues. In this paper, to alleviate the over-smoothing issue, we propose a soft graph normalization method to preserve the diversities of node embeddings and prevent indiscrimination due to possible over-closeness. Combined with residual connections, we analyze the reason why the method can effectively capture the knowledge in both input graph structures and node features even with deep networks. Additionally, inspired by Curriculum Learning that learns easy examples before the hard ones, we propose a novel label-smoothing-based learning framework to enhance the optimization of deep GNNs, which iteratively smooths labels in an auxiliary graph and constructs many gradual non-smooth tasks for extracting increasingly complex knowledge and gradually discriminating nodes from coarse to fine. The method arguably reduces the risk of overfitting and generalizes better results. Finally, extensive experiments are carried out to demonstrate the effectiveness and potential of the proposed model and learning framework through comparison with twelve existing baselines including the state-of-the-art methods on twelve real-world node classification benchmarks.

PDF Details DOI

AAAI Conference 2024 Conference Paper

Efficient Constrained K-center Clustering with Background Knowledge

Longkun Guo
Chaoqi Jia
Kewen Liao
Zhigang Lu
Minhui Xue

Center-based clustering has attracted significant research interest from both theory and practice. In many practical applications, input data often contain background knowledge that can be used to improve clustering results. In this work, we build on widely adopted k-center clustering and model its input background knowledge as must-link (ML) and cannot-link (CL) constraint sets. However, most clustering problems including k-center are inherently NP-hard, while the more complex constrained variants are known to suffer severer approximation and computation barriers that significantly limit their applicability. By employing a suite of techniques including reverse dominating sets, linear programming (LP) integral polyhedron, and LP duality, we arrive at the first efficient approximation algorithm for constrained k-center with the best possible ratio of 2. We also construct competitive baseline algorithms and empirically evaluate our approximation algorithm against them on a variety of real datasets. The results validate our theoretical findings and demonstrate the great advantages of our algorithm in terms of clustering cost, clustering quality, and running time.

PDF Details DOI

TCS Journal 2023 Journal Article

Approximation algorithm for MinSum linear barrier coverage with sink-based mobile sensors on the plane

Wenjie Zou
Longkun Guo
Chunlin Hao
Lei Liu

Emerging wireless and mobile applications, such as border intrusion detection with station-based drones, brought a new barrier coverage problem of using sink-based mobile sensors to cover a given line barrier with minimum energy consumption. In this paper, we focus on the uniform sink-based line barrier coverage (SLBC) problem, in which we are given a line barrier and k sink stations distributed on the plane which can emit an infinite number of sensors with an identical sensing radius. The problem aims to find their final positions on the barrier for the sensors emitted by the stations, such that the total moving distance of the sensors is minimized and each point of the barrier is within the sensing area of at least one sensor. We first observe the geometric structure of an optimal solution that any optimal solution can be considered as a set of intersecting tangent (disk) segments, where a tangent (disk) segment is a sequence of tangent disks. Then, we devise an algorithm to calculate all possible tangent (disk) segments and another algorithm to calculate the near-optimal positions for each of such segments. After computing all tangent (disk) segments and their near-optimal positions, an algorithm is proposed to transform uniform SLBC into an instance of the shortest path problem. It is shown the whole algorithm deserves a runtime O ( k 2 log ⁡ k r ε ) and consumes at most ε more movement than an optimal solution, where ε is any given positive real number, and r and k are the sensor radius and the number of sink stations, respectively.

Details DOI

TCS Journal 2023 Journal Article

Submodular maximization over data streams with differential privacy noise

Longkun Guo
Kewen Liao
Di Xiao
Pei Yao

In the big data era, data often comes in the form of streams and fast data stream analysis has recently attracted intensive research interest. Submodular optimization naturally appears in many streaming data applications such as social network influence maximization with the property of diminishing returns. However, in a practical setting, streaming data frequently comes with noises that are small but significant enough to impact the optimality of submodular optimization solutions. Following the framework of differential privacy (DP), this paper considers a streaming model with DP noise that is small by construction. Within this noisy streaming model, the paper strives to address the general problem of submodular maximization with a cardinality constraint. The main theoretical result we obtained is a streaming algorithm that is one-pass and has an approximation guarantee of 1 ( 2 + ( 1 + 1 k ) 2 ) ( 1 + 1 k ) − δ for any δ > 0. Finally, we implement the algorithm and evaluate it against several baseline methods. Numerical results support the practical performance of our algorithm across several real datasets.

Details DOI

TCS Journal 2021 Journal Article

Deterministic approximation algorithm for submodular maximization subject to a matroid constraint

Xin Sun
Dachuan Xu
Longkun Guo
Min Li

In this paper, we study the generalized submodular maximization problem with a non-negative monotone submodular set function as the objective function and subject to a matroid constraint. The problem is generalized through the curvature parameter α ∈ [ 0, 1 ] which measures how far a set function deviates from linearity to submodularity. We propose a deterministic approximation algorithm which uses the approximation algorithm proposed by Buchbinder et al. [2] as a building block and inherits the approximation guarantee for α = 1. For general value of the curvature parameter α ∈ [ 0, 1 ], we present an approximation algorithm with a factor of 1 + h α ( y ) + Δ ⋅ [ 3 + α − ( 2 + α ) y − ( 1 + α ) h α ( y ) ] 2 + α + ( 1 + α ) ( 1 − y ), where y ∈ [ 0, 1 ] is a predefined parameter for tuning the ratio. In particular, when α = 1 we obtain a ratio 0. 5008 when setting y = 0. 9, coinciding with the renowned state-of-art approximate ratio; when α = 0 that the object is a linear function, the approximation factor equals one and our algorithm is indeed an exact algorithm that always produces optimum solutions.

Details DOI

TCS Journal 2021 Journal Article

On finding maximum disjoint paths with different colors: Computational complexity and practical LP-based algorithms

Yunyun Deng
Longkun Guo
Kewen Liao
Yi Chen

With the rapid development of wireless networks, the burden on data transmission is becoming much higher, so are the requirements for bandwidth and load balancing. To cope with these changing requirements, we investigate a novel problem of finding maximum disjoint paths with different colors (MDPDC). In MDPDC, transmission frequencies in a network are modeled as different colors on network nodes. The aim is to find a maximum number of color-constrained node-disjoint paths where nodes must share the same color within any disjoint path, and differ in color among different disjoint paths. For this proposed problem, we first prove MDPDC is NP -complete in both directed and undirected graphs. Then we provide two practical linear programming based solutions with theoretical justifications of their correctness and time complexity. Extensive computer experiments are also carried out with several compared baseline methods to demonstrate the effectiveness of proposed algorithms both in running time and solution quality.

Details DOI

TCS Journal 2021 Journal Article

Parallelized maximization of nonsubmodular function subject to a cardinality constraint

Hongxiang Zhang
Dachuan Xu
Longkun Guo
Jingjing Tan

In the paper, we consider the problem of maximizing the multilinear extension of a nonsubmodular set function subject to a k-cardinality constraint with adaptive rounds of evaluation queries. We devise an algorithm which achieves a ratio of ( 1 − e − γ 2 − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds and O ( n log ⁡ n / ϵ 2 ) queries, where γ is the continuous generic submodularity ratio that compares favorably in flexibility to the traditional submodularity ratio proposed by Das and Kempe. The key idea of our algorithm is originated from the parallel-greedy algorithm proposed by Chekuri et al. , but incorporating with two major changes to retain the performance guarantee: First, identify all good coordinates with the continuous generic submodularity ratio and gradient values approximately as large as the best coordinate, and increase along all these coordinates uniformly; Second, increase x along these coordinates by a dynamical increment whose value depends on γ. The key difficulty of our algorithm is that when the function is nonsubmodular, the set of the best coordinate does not decrease during iterations; while provided submodularity, the decreasing can be ensured by the parallel-greedy algorithm. Our algorithms slightly compromise performance guarantee for the sake of extending to constrained nonsubmodular maximization with parallelism, provided that the state-of-art algorithm for the corresponding submodular version attains an approximation ratio of ( 1 − 1 / e − ϵ ) and requires O ( log ⁡ n / ϵ 2 ) adaptive rounds.

Details DOI

TCS Journal 2019 Journal Article

Efficient approximation algorithms for maximum coverage with group budget constraints

Longkun Guo
Min Li
Dachuan Xu

Given a ground set U with a non-negative weight w i for each i ∈ U, a positive integer k and a collection of sets S, which is partitioned into a family of disjoint groups G, the goal of the Maximum Coverage problem with Group budget constraints (MCG) is to select k sets from S, such that the total weight of the union of the k sets is maximized and at most one set is selected from each group G ∈ G. We first present an approximation algorithm with a factor 1 − 1 e and an exponential time via randomized linear programming rounding technique. Then we improve the time complexity of the algorithm to O ( ( m + n ) 3. 5 L + k 3. 5 q 7 L ) for | S | = m, | U | = n, and L being the length of the input, by the key idea of modeling the selection of groups as computing a constrained flow in a corresponding auxiliary graph. The algorithm is later shown can be extended to solve two generalizations of MCG. Last but not the least, we present another algorithm with a time complexity O ( ( m + n ) 3. 5 L + k δ 10. 5 L ) and a slightly increased approximation ratio 1 − e 1 δ − 1 mainly based on the idea of partition, where δ ≥ 2 is a parameter tuning which can balance the time complexity and the ratio.

Details DOI

IJCAI Conference 2018 Conference Paper

A Fast Algorithm for Optimally Finding Partially Disjoint Shortest Paths

Longkun Guo
Yunyun Deng
Kewen Liao
Qiang He
Timos Sellis
Zheshan Hu

The classical disjoint shortest path problem has recently recalled interests from researchers in the network planning and optimization community. However, the requirement of the shortest paths being completely vertex or edge disjoint might be too restrictive and demands much more resources in a network. Partially disjoint shortest paths, in which a bounded number of shared vertices or edges is allowed, balance between degree of disjointness and occupied network resources. In this paper, we consider the problem of finding k shortest paths which are edge disjoint but partially vertex disjoint. For a pair of distinct vertices in a network graph, the problem aims to optimally find k edge disjoint shortest paths among which at most a bounded number of vertices are shared by at least two paths. In particular, we present novel techniques for exactly solving the problem with a runtime that significantly improves the current best result. The proposed algorithm is also validated by computer experiments on both synthetic and real networks which demonstrate its superior efficiency of up to three orders of magnitude faster than the state of the art.

PDF Details

TCS Journal 2015 Journal Article

Improved approximation algorithms for constrained fault-tolerant resource allocation

Kewen Liao
Hong Shen
Longkun Guo

In Constrained Fault-Tolerant Resource Allocation (FTRA) problem, we are given a set of sites containing facilities as resources and a set of clients accessing these resources. Each site i can open at most R i facilities with opening cost f i. Each client j requires an allocation of r j open facilities and connecting j to any facility at site i incurs a connection cost c i j. The goal is to minimize the total cost of this resource allocation scenario. FTRA generalizes the Unconstrained Fault-Tolerant Resource Allocation ( FTRA ∞ ) [1] and the classical Fault-Tolerant Facility Location (FTFL) [2] problems: for every site i, FTRA ∞ does not have the constraint R i, whereas FTFL sets R i = 1. These problems are said to be uniform if all r j 's are the same, and general otherwise. For the general metric FTRA, we first give an LP-rounding algorithm achieving an approximation ratio of 4. Then we show the problem reduces to FTFL, implying the ratio of 1. 7245 from [3]. For the uniform FTRA, we provide a 1. 52-approximation primal–dual algorithm in O ( n 4 ) time, where n is the total number of sites and clients.

Details DOI

TCS Journal 2012 Journal Article

On the complexity of the edge-disjoint min–min problem in planar digraphs

Longkun Guo
Hong Shen

The min–min problem of finding a disjoint path pair with the length of the shorter path minimized is known to be NP-complete (Xu et al. , 2006) [1]. In this paper, we prove that in planar digraphs the edge-disjoint min–min problem remains NP-complete and admits no K -approximation for any K > 1 unless P = N P. As a by-product, we show that this problem remains NP-complete even when all edge costs are equal (i. e. , stronglyNP-complete). To our knowledge, this is the first NP-completeness proof for the edge-disjoint min–min problem in planar digraphs.

Details DOI