A graph attention-based policy gradient method with an adaptive embedding strategy for k-center problems

Abstract

The k-center problem (KCP) is a well-known NP-hard combinatorial optimization challenge in the field of computer science and operations research, aiming to determine optimal locations for k centers within a given set of nodes to minimize the maximum distance from each node to its nearest center. In contrast to conventional algorithms that have inherent limitations in handling the trade-off between solution quality and computational efficiency, this study proposes a new method based on a graph attention mechanism with an encoder-decoder architecture to find high-quality solutions for KCPs by directly learning heuristics from the graph. Specifically, the encoder processes the input feature of the graph and capture intricate spatial patterns and dependencies among nodes, whereas the decoder leverages the encoded information and attention weights to iteratively generate solutions for the KCP. Moreover, an adaptive embedding strategy is developed to handle the specific attributes and constraints inherent in different KCP instances. To find high-quality solutions, a policy gradient method with an exponential moving average baseline is developed to update and learn the optimal model parameters. A comprehensive set of experiments on multiple problem sizes are conducted to systematically compared the performance of the proposed method with a wide range of baseline methods across four types of KCPs, including the standard KCP, capacitated KCP, non-uniform KCP, and dynamic KCP. The experimental results demonstrate the competitive performance of the graph attention-based method in addressing KCPs.