Approximation Algorithm for Connected Submodular Function Maximization Problems

In this paper, we study a connected submodular function maximization problem, which arises from many applications including deploying UAV networks to serve users and placing sensors to cover Points of Interest (PoIs). Specifically, given a budget K, the problem is to find a subset S with K nodes from a graph G so that a given submodular function f(S) on S is maximized while the induced subgraph G[S] by the nodes in S is connected, where the submodular function f can be used to model many practical application problems, such as the number of users within different service areas of the deployed UAVs in S, the sum of data rates of users served by the UAVs, the number of covered PoIs by placed sensors, etc. We then propose a novel 1-1/e/2h+2 -approximation algorithm for the problem, improving the best approximation ratio 1-1/e/2h+3 for the problem so far, through estimating a novel upper bound on the problem and designing a smart graph decomposition technique, where e is the base of the natural logarithm, h is a parameter depends on the problem and its typical value is 2. In addition. when h = 2, the algorithm approximation ratio is at least 1-1/e/5 and may be as large as 1 in some special cases when K ≤ 21, and is no less than 1-1/e/6 when K ≥ 22, compared with the current best approximation ratio 1-1/e/7(= 1-1/e/2h+3) for the problem. We finally evaluate the algorithm performance in the application of deploying a UAV network. Experimental results demonstrate the number of users within the service area of the deployed UAV network by the proposed algorithm is up to 7.5% larger than those by existing algorithms, and its empirical approximation ratio is between 0.7 and 0.99, which is close to the theoretical maximum value one. © 2024 IEEE.