Query：
学者姓名：郭龙坤
Refining：
Year
Type
Indexed by
Source
Complex
Former Name
Co-
Language
Clean All
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 等. "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 ：
Emerging applications are imposing challenges for incorporating fairness constraints into k-center clustering in the streaming setting. Different from the traditional k-center problem, the fairness constraints require that the input points be divided into disjoint groups and the number of centers from each group is constrained by a given upper bound. Moreover, observing the applications of fair k-center inmassive datasets, we consider the problem in the streaming setting, where the data points arrive in a streaming manner that each point can be processed at its arrival. As themain contributions, we propose a two-pass streaming algorithm for the fair k-center problem with two groups, achieving an approximation ratio of 3 + epsilon and consuming only O(k log n) memory and O(k) update time, matching the state-of-art ratio for the offline setting. Then, we show that the algorithm can be easily improved to a one-pass streaming algorithm with an approximation ratio of 7+ epsilon and the same memory complexity and update time. Moreover, we show that our algorithm can be simply tuned to solve the case with an arbitrary number of groups while achieving the same ratio and space complexity. Lastly, we carried out extensive experiments to evaluate the practical performance of our algorithm compared with the state-of-the-art algorithms.
Keyword ：
Approximation algorithm Approximation algorithm Fair k-center clustering Fair k-center clustering Streaming algorithm Streaming algorithm
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Lin, Zeyu , Guo, Longkun , Jia, Chaoqi . Streaming Fair k-Center Clustering over Massive Dataset with Performance Guarantee [J]. | ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PT III, PAKDD 2024 , 2024 , 14647 : 105-117 . |
| MLA | Lin, Zeyu 等. "Streaming Fair k-Center Clustering over Massive Dataset with Performance Guarantee" . | ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PT III, PAKDD 2024 14647 (2024) : 105-117 . |
| APA | Lin, Zeyu , Guo, Longkun , Jia, Chaoqi . Streaming Fair k-Center Clustering over Massive Dataset with Performance Guarantee . | ADVANCES IN KNOWLEDGE DISCOVERY AND DATA MINING, PT III, PAKDD 2024 , 2024 , 14647 , 105-117 . |
| 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 ：
This special issue is closely associated with the 17th Annual Conference on Theory and Applications of Models of Computation (TAMC), held in Tianjin, China, from September 16 to 18, 2022. Featuring a selection of eight remarkable papers, six of which originated from contributors to TAMC 2022, this issue underwent a rigorous selection process, upholding the stringent external review standards of Tsinghua Science and Technology. Our aim is to showcase recent advancements and chart future directions in computational model theory and applications. The papers cover a diverse range of topics, including submodular optimization, approximation algorithms, complexity theory, algorithmic coding, number theory, differential privacy, and more.
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Guo, Longkun , Ji, Sai . The Editorial [J]. | TSINGHUA SCIENCE AND TECHNOLOGY , 2024 , 29 (6) : 0i-0i . |
| MLA | Guo, Longkun et al. "The Editorial" . | TSINGHUA SCIENCE AND TECHNOLOGY 29 . 6 (2024) : 0i-0i . |
| APA | Guo, Longkun , Ji, Sai . The Editorial . | TSINGHUA SCIENCE AND TECHNOLOGY , 2024 , 29 (6) , 0i-0i . |
| 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 ：
Given a set X of n points in a metric space and a radius R, we consider the combining version of k-center and k-median which is with the same objective as k-median, but with the constraint that any x in X is assigned to a center within the range R. In this paper, we propose a bicriteria approximation algorithm achieving a bicriteria approximation ratio of (3 + epsilon, 7), by incorporating local search with the technology of finding key balls with consequent center exchanges therein. Compared to the state-of-the-art approximation ratio of (8, 4) that is based on an LP formulation for k-median, we improve the ratio of the total distance from 8 to 3 + epsilon at the price of compromising the ratio of radius 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 . A Local Search Algorithm for Radius-Constrained k-Median [J]. | THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024 , 2024 , 14637 : 173-184 . |
| MLA | Chi, Gaojie et al. "A Local Search Algorithm for Radius-Constrained k-Median" . | THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024 14637 (2024) : 173-184 . |
| APA | Chi, Gaojie , Guo, Longkun . A Local Search Algorithm for Radius-Constrained k-Median . | THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024 , 2024 , 14637 , 173-184 . |
| 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 ：
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 ：
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.
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 [J]. | THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 12 , 2024 : 13528-13536 . |
| MLA | Li, Jin et al. "Curriculum-Enhanced Residual Soft An-Isotropic Normalization for Over-Smoothness in Deep GNNs" . | THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 12 (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 . | THIRTY-EIGHTH AAAI CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOL 38 NO 12 , 2024 , 13528-13536 . |
| Export to | NoteExpress RIS BibTex |
Version ：
Export
| Results： |
Selected to |
| Format： |
