Query：
学者姓名：郭龙坤
Refining：
Year
Type
Indexed by
Source
Complex
Co-
Language
Clean All
Abstract ：
Many practical applications impose a new challenge of utilizing instance-level background knowledge (e.g., subsets of similar or dissimilar data points) within their input data to improve clustering results. In this work, we build on the widely adopted k-center clustering, modeling its input instance-level background knowledge as must-link (ML) and cannot-link (CL) constraint sets, and formulate the constrained k-center problem. Given the long-standing challenge of developing efficient algorithms for constrained clustering problems, we first derive an efficient approximation algorithm for constrained k-center at the best possible approximation ratio of 2 with linear programming (LP)-rounding technology. Recognizing the limitations of LP-rounding algorithms including high runtime complexity and challenges in parallelization, we subsequently develop a greedy algorithm that does not rely on the LP and can be efficiently parallelized. This algorithm also achieves the same approximation ratio 2 but with lower runtime complexity. Lastly, we empirically evaluate our approximation algorithm against baselines on various real datasets, validating our theoretical findings and demonstrating significant advantages of our algorithm in terms of clustering cost, quality, and runtime complexity.
Keyword ：
Approximation algorithm Approximation algorithm Approximation algorithms Approximation algorithms Australia Australia Bipartite graph Bipartite graph Clustering algorithms Clustering algorithms constrained clustering constrained clustering greedy algorithm greedy algorithm Greedy algorithms Greedy algorithms Heuristic algorithms Heuristic algorithms k-center k-center Linear programming Linear programming linear programming (LP)-rounding linear programming (LP)-rounding Measurement Measurement Polynomials Polynomials Runtime Runtime
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Guo, Longkun , Jia, Chaoqi , Liao, Kewen et al. Near-Optimal Algorithms for Instance-Level Constrained k-Center Clustering [J]. | IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS , 2025 . |
| MLA | Guo, Longkun et al. "Near-Optimal Algorithms for Instance-Level Constrained k-Center Clustering" . | IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS (2025) . |
| APA | Guo, Longkun , Jia, Chaoqi , Liao, Kewen , Lu, Zhigang , Xue, Minhui . Near-Optimal Algorithms for Instance-Level Constrained k-Center Clustering . | IEEE TRANSACTIONS ON NEURAL NETWORKS AND LEARNING SYSTEMS , 2025 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
The rapid growth of cloud computing has brought new challenges in Parallel Batch Machine Scheduling (PBMS), particularly when incorporating malleability and rejection constraints. This has led to the Parallel Batch Machine Scheduling with Malleability and Rejection problem (PBMSMR), which involves malleable jobs whose widths can be adjusted during execution within specified limits and incorporates job rejection subject to a penalty threshold. Based on an analysis of key properties of batch scheduling with job rejection, we develop an approximation algorithm for PBMSMR by employing a greedy approach that reorders and iteratively refines job sets to minimize the objective while respecting rejection constraints. The algorithm achieves a time complexity of O(n2logn) and an approximation ratio of (4-2Km), where K and m denote the capacities and the number of the machines, respectively. For jobs with identical release times, we fine-tune the algorithm to achieve an approximation ratio of (3+2(K-1)Km). Additionally, for PBMS with two machines of non-identical capacities and fixed-width jobs, we achieve a ratio of 175 with O(nlogn), improving upon the previous state-of-the-art approximation ratio of 5 with a runtime of O(n2). © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.
Keyword ：
Approximation algorithms Approximation algorithms Job shop scheduling Job shop scheduling Scheduling algorithms Scheduling algorithms
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Xia, Fenghe , Guo, Longkun , Zhang, Xiaoyan . Fast Approximation for Scheduling Malleable Jobs on Parallel Batch Machines with Rejection [C] . 2025 : 216-222 . |
| MLA | Xia, Fenghe et al. "Fast Approximation for Scheduling Malleable Jobs on Parallel Batch Machines with Rejection" . (2025) : 216-222 . |
| APA | Xia, Fenghe , Guo, Longkun , Zhang, Xiaoyan . Fast Approximation for Scheduling Malleable Jobs on Parallel Batch Machines with Rejection . (2025) : 216-222 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Streaming fair submodular maximization is attracting considerable research interest due to its broad applications in machine learning, particularly for tasks such as feature selection and text summary against large-scale data and fairness considerations. Given a sequence of data points belonging to distinct groups and arriving in a streaming manner, the problem aims to select k data points from the stream to maximize the total revenue of the selected points. In this paper, we first devise an efficient (12-Ε)-approximation algorithm with O(log(1ΕlogkΕ)) passes, an improvement over the previous O(1ΕlogkΕ) passes. Then, we present a 13-Ε-approximation algorithm that needs only one pass and consumes a buffer of size O(k+|B|) and achieves a ratio strictly greater than 14 while using a buffer of size O(klogk). Lastly, we conduct extensive experiments using real-world datasets to validate our method, demonstrating that it outperforms all state-of-the-art algorithms in terms of efficiency, effectiveness, and scalability. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2025.
Keyword ：
Approximation algorithms Approximation algorithms Large datasets Large datasets
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zhu, Shuqian , Guo, Longkun , Lin, Jiawei . Fair Maximization of Monotone Submodular Functions in Data Streams [C] . 2025 : 287-298 . |
| MLA | Zhu, Shuqian et al. "Fair Maximization of Monotone Submodular Functions in Data Streams" . (2025) : 287-298 . |
| APA | Zhu, Shuqian , Guo, Longkun , Lin, Jiawei . Fair Maximization of Monotone Submodular Functions in Data Streams . (2025) : 287-298 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Given a radius R is an element of Z+\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$R\in \mathbb {Z}<^>+$$\end{document} and a set X of n points distributed within a metric space, we consider the radius-constrained k-median problem, which combines both the k-center and k-median clustering problems. In this problem, the objective is the same as that of the k-median problem, with the additional constraint that every point x in X must be assigned to a center within the given radius R. This paper proposes an approximation algorithm that achieves a bicriteria approximation ratio of (3+epsilon,7)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(3+\varepsilon , 7)$$\end{document} by incorporating local search with a key ball structure. The algorithm constructs a keyball center set to ensure coverage of the points and iteratively refines the solution through subset swaps while satisfying feasibility conditions. Thus, this process maintains coverage while reducing costs. Compared to the state-of-the-art approximation ratio of (8, 4) based on a linear programming formulation for this problem, our approach improves the k-median ratio from 8 to 3+epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$3+\varepsilon $$\end{document}, at the cost of increasing the radius ratio from 4 to 7.
Keyword ：
Approximation algorithm Approximation algorithm k-center k-center k-median k-median Local search Local search
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Chi, Gaojie , Guo, Longkun , Jia, Chaoqi . A Local Search Algorithm for the Radius-Constrained k-Median Problem [J]. | THEORY OF COMPUTING SYSTEMS , 2025 , 69 (1) . |
| MLA | Chi, Gaojie et al. "A Local Search Algorithm for the Radius-Constrained k-Median Problem" . | THEORY OF COMPUTING SYSTEMS 69 . 1 (2025) . |
| APA | Chi, Gaojie , Guo, Longkun , Jia, Chaoqi . A Local Search Algorithm for the Radius-Constrained k-Median Problem . | THEORY OF COMPUTING SYSTEMS , 2025 , 69 (1) . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
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. Copyright © 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Keyword ：
Curricula Curricula Graphic methods Graphic methods Graph neural networks Graph neural networks Graph structures Graph structures Graph theory Graph theory Iterative methods Iterative methods Learning systems Learning systems
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Li, Jin , Zhang, Qirong , Xu, Shuling et al. Curriculum-Enhanced Residual Soft An-Isotropic Normalization for Over-Smoothness in Deep GNNs [C] . 2024 : 13528-13536 . |
| MLA | Li, Jin et al. "Curriculum-Enhanced Residual Soft An-Isotropic Normalization for Over-Smoothness in Deep GNNs" . (2024) : 13528-13536 . |
| APA | Li, Jin , Zhang, Qirong , Xu, Shuling , Chen, Xinlong , Guo, Longkun , Fu, Yang-Geng . Curriculum-Enhanced Residual Soft An-Isotropic Normalization for Over-Smoothness in Deep GNNs . (2024) : 13528-13536 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
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. Copyright © 2024, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.
Keyword ：
Approximation algorithms Approximation algorithms Artificial intelligence Artificial intelligence Clustering algorithms Clustering algorithms Computation theory Computation theory Linear programming Linear programming
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Guo, Longkun , Jia, Chaoqi , Liao, Kewen et al. Efficient Constrained K-center Clustering with Background Knowledge [C] . 2024 : 20709-20717 . |
| MLA | Guo, Longkun et al. "Efficient Constrained K-center Clustering with Background Knowledge" . (2024) : 20709-20717 . |
| APA | Guo, Longkun , Jia, Chaoqi , Liao, Kewen , Lu, Zhigang , Xue, Minhui . Efficient Constrained K-center Clustering with Background Knowledge . (2024) : 20709-20717 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
基于云原生数据库的许多应用场景需要处理海量的数据流. 为了实时分析数据流中的群体趋势信息而又不泄露单个用户的隐私，这些应用需要在每个时刻都可以为数据流中的最近数据集快速创建可以安全发布的差分隐私直方图. 然而，现有的直方图发布方法因缺乏高效数据结构，导致无法快速提取关键信息以确保数据的实时可用性. 为解决此问题，深入分析数据采样与隐私保护之间的关系，提出基于采样的数据流差分隐私快速发布算法SPF（sampling based fast publishing algorithm with differential privacy for data stream）. SPF首创高效数据流采样草图结构（efficient data stream sampling sketch structure，EDS），EDS对滑动窗口内数据进行采样统计估计，并过滤不合理数据，实现了对关键信息的快速提取. 然后，证明EDS结构输出的近似值理论上等效于对真实值添加差分隐私噪声. 最后，为了满足用户所提供的隐私保护强度，并且避免正确反映原始数据流的真实情况，提出了一种基于高效数据流采样的自适应加噪算法. 根据用户的隐私保护强度和EDS结构所提供的隐私保护强度之间的关系，通过隐私分配的方式自适应生成最终可发布直方图. 实验证明，相较于现有算法，SPF在保持相同数据可用性的前提下显著降低了时间和空间开销.
Keyword ：
云原生数据库 云原生数据库 差分隐私 差分隐私 数据发布 数据发布 数据流 数据流 数据采样 数据采样 滑动窗口 滑动窗口
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | 王修君 , 莫磊 , 郑啸 et al. 基于采样的数据流差分隐私快速发布算法 [J]. | 计算机研究与发展 , 2024 , 61 (10) : 2433-2447 . |
| MLA | 王修君 et al. "基于采样的数据流差分隐私快速发布算法" . | 计算机研究与发展 61 . 10 (2024) : 2433-2447 . |
| APA | 王修君 , 莫磊 , 郑啸 , 卫琳娜 , 董俊 , 刘志 et al. 基于采样的数据流差分隐私快速发布算法 . | 计算机研究与发展 , 2024 , 61 (10) , 2433-2447 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
Many cloud native database applications need to handle massive data streams. To analyze group trend information in these data streams in real time without compromising individual user privacy, these applications require the capability to quickly create differentially private histograms for the most recent dataset at any given moment. However, existing histogram publishing methods lack efficient data structures, making it difficult to rapidly extract key information to ensure real-time data usability. To address this issue, we deeply analyze the relationship between data sampling and privacy protection, and propose a sampling based fast publishing algorithm with differential privacy for data stream (SPF). SPF introduces an efficient data stream sampling sketch structure (EDS) for the first time, which samples and statistically estimates data within a sliding window and filters out unreasonable data, enabling rapid extraction of key information. Then, we demonstrate that the approximations output by the EDS structure are theoretically equivalent to adding differential privacy noise to the true values. Finally, to meet the privacy protection strength provided by the user while reflecting the true situation of the original data stream, an adaptive noise addition algorithm based on efficient data stream sampling is proposed. According to the relationship between the user-provided privacy protection strength and the privacy protection strength provided by the EDS structure, the algorithm adaptively generates the final publishable histogram through privacy allocation. Experiments show that compared with existing algorithms, SPF significantly reduces time and space overhead while maintaining the same data usability. © 2024 Science Press. All rights reserved.
Keyword ：
Differential privacy Differential privacy
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Wang, Xiujun , Mo, Lei , Zheng, Xiao et al. Sampling Based Fast Publishing Algorithm with Differential Privacy for Data Stream [J]. | Computer Research and Development , 2024 , 61 (10) : 2433-2447 . |
| MLA | Wang, Xiujun et al. "Sampling Based Fast Publishing Algorithm with Differential Privacy for Data Stream" . | Computer Research and Development 61 . 10 (2024) : 2433-2447 . |
| APA | Wang, Xiujun , Mo, Lei , Zheng, Xiao , Wei, Linna , Dong, Jun , Liu, Zhi et al. Sampling Based Fast Publishing Algorithm with Differential Privacy for Data Stream . | Computer Research and Development , 2024 , 61 (10) , 2433-2447 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
The use of deep reinforcement learning (DRL) techniques to solve classical combinatorial optimization problems like the Traveling Salesman Problem (TSP) has garnered considerable attention due to its advantage of flexible and fast model-based inference. However, DRL training often suffers low efficiency and scalability, which hinders model generalization. This paper proposes a simple yet effective pre-training method that utilizes behavior cloning to initialize neural network parameters for policy gradient DRL. To alleviate the need for large amounts of demonstrations in behavior cloning, we exploit the symmetry of TSP solutions for augmentation. Our method is demonstrated by enhancing the state-of-the-art policy gradient models Attention and POMO for the TSP. Experimental results show that the optimality gap of the solution is significantly reduced while the DRL training time is greatly shortened. This also enables effective and efficient solving of larger TSP instances.
Keyword ：
behavior cloning behavior cloning deep reinforcement learning deep reinforcement learning policy gradient policy gradient Traveling salesman problem Traveling salesman problem
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zhang, Yunchao , Liao, Kewen , Liao, Zhibin et al. Enhancing Policy Gradient for Traveling Salesman Problem with Data Augmented Behavior Cloning [J]. | ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PT II, PAKDD 2024 , 2024 , 14646 : 327-338 . |
| MLA | Zhang, Yunchao et al. "Enhancing Policy Gradient for Traveling Salesman Problem with Data Augmented Behavior Cloning" . | ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PT II, PAKDD 2024 14646 (2024) : 327-338 . |
| APA | Zhang, Yunchao , Liao, Kewen , Liao, Zhibin , Guo, Longkun . Enhancing Policy Gradient for Traveling Salesman Problem with Data Augmented Behavior Cloning . | ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PT II, PAKDD 2024 , 2024 , 14646 , 327-338 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Abstract ：
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.
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Guo, Longkun , Jia, Chaoqi , Liao, Kewen et al. Efficient Constrained K-center Clustering with Background Knowledge [J]. | THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 18 , 2024 : 20709-20717 . |
| MLA | Guo, Longkun et al. "Efficient Constrained K-center Clustering with Background Knowledge" . | THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 18 (2024) : 20709-20717 . |
| APA | Guo, Longkun , Jia, Chaoqi , Liao, Kewen , Lu, Zhigang , Xue, Minhui . Efficient Constrained K-center Clustering with Background Knowledge . | THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 18 , 2024 , 20709-20717 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Export
| Results： |
Selected to |
| Format： |
