Query：
学者姓名：郭龙坤
Refining：
Year
Type
Indexed by
Source
Complex
Former Name
Co-
Language
Clean All
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 等. "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 ：
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 ：
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 等. "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 ：
As a promising technique for offloading computation tasks from mobile devices, Unmanned Aerial Vehicle (UAV)-assisted Mobile Edge Computing (MEC) utilizes UAVs as computational resources. A popular method for enhancing the quality of service (QoS) of UAV-assisted MEC systems is to jointly optimize UAV deployment and computation task offloading. This imposes the challenge of dynamically adjusting UAV deployment and computation offloading to accommodate the changing positions and computational requirements of mobile devices. Due to the real-time requirements of MEC computation tasks, finding an efficient joint optimization approach is imperative. This paper proposes an algorithm aimed at minimizing the average response delay in a UAV-assisted MEC system. The approach revolves around the joint optimization of UAV deployment and computation offloading through convex optimization. We break down the problem into three sub-problems: UAV deployment, Ground Device (GD) access, and computation tasks offloading, which we address using the block coordinate descent algorithm. Observing the $NP$NP-hardness nature of the original problem, we present near-optimal solutions to the decomposed sub-problems. Simulation results demonstrate that our approach can generate a joint optimization solution within seconds and diminish the average response delay compared to state-of-the-art algorithms and other advanced algorithms, with improvements ranging from 4.70% to 42.94%.
Keyword ：
Autonomous aerial vehicles Autonomous aerial vehicles Block coordinate descent Block coordinate descent Cloud computing Cloud computing computation offloading computation offloading Computer architecture Computer architecture Delays Delays Heuristic algorithms Heuristic algorithms mobile edge computing mobile edge computing Mobile handsets Mobile handsets Multi-access edge computing Multi-access edge computing Optimization Optimization Relays Relays Servers Servers unmanned aerial vehicle deployment unmanned aerial vehicle deployment
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Zhang, Jianshan , Luo, Haibo , Chen, Xing et al. Minimizing Response Delay in UAV-Assisted Mobile Edge Computing by Joint UAV Deployment and Computation Offloading [J]. | IEEE TRANSACTIONS ON CLOUD COMPUTING , 2024 , 12 (4) : 1372-1386 . |
| MLA | Zhang, Jianshan et al. "Minimizing Response Delay in UAV-Assisted Mobile Edge Computing by Joint UAV Deployment and Computation Offloading" . | IEEE TRANSACTIONS ON CLOUD COMPUTING 12 . 4 (2024) : 1372-1386 . |
| APA | Zhang, Jianshan , Luo, Haibo , Chen, Xing , Shen, Hong , Guo, Longkun . Minimizing Response Delay in UAV-Assisted Mobile Edge Computing by Joint UAV Deployment and Computation Offloading . | IEEE TRANSACTIONS ON CLOUD COMPUTING , 2024 , 12 (4) , 1372-1386 . |
| 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 ：
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 ：
Emerging applications in Printed Circuit Board (PCB) routing impose new challenges on automatic length matching, including adaptability for any-direction traces with their original routing preserved for interactiveness. The challenges can be addressed through two orthogonal stages: assign non-overlapping routing regions to each trace and meander the traces within their regions to reach the target length. In this paper, mainly focusing on the meandering stage, we propose an obstacle-aware detailed routing approach to optimize the utilization of available space and achieve length matching while maintaining the original routing of traces. Furthermore, our approach incorporating the proposed Multi-Scale Dynamic Time Warping (MSDTW) method can also handle differential pairs against common decoupled problems. Experimental results demonstrate that our approach has effective length-matching routing ability and compares favorably to previous approaches under more complicated constraints. © 2024 Copyright is held by the owner/author(s). Publication rights licensed to ACM.
Keyword ：
Dynamic routing algorithms Dynamic routing algorithms Program debugging Program debugging
Cite：
Copy from the list or Export to your reference management。
| GB/T 7714 | Fang, Weijie , Guo, Longkun , Lin, Jiawei et al. Obstacle-Aware Length-Matching Routing for Any-Direction Traces in Printed Circuit Board [C] . 2024 . |
| MLA | Fang, Weijie et al. "Obstacle-Aware Length-Matching Routing for Any-Direction Traces in Printed Circuit Board" . (2024) . |
| APA | Fang, Weijie , Guo, Longkun , Lin, Jiawei , Xiong, Silu , He, Huan , Xu, Jiacen et al. Obstacle-Aware Length-Matching Routing for Any-Direction Traces in Printed Circuit Board . (2024) . |
| 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 ：
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 ：
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 et al. "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 ：
Export
| Results： |
Selected to |
| Format： |
