Abstract
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.
Recommended Citation
W. Xu et al., "Approximation Algorithm for Connected Submodular Function Maximization Problems," Proceedings - International Conference on Distributed Computing Systems, pp. 1108 - 1118, Institute of Electrical and Electronics Engineers, Jan 2024.
The definitive version is available at https://doi.org/10.1109/ICDCS60910.2024.00106
Department(s)
Computer Science
Keywords and Phrases
approximation algorithms; sensor placement; submod-ular function maximization; UAV deployment
International Standard Serial Number (ISSN)
2575-8411; 1063-6927
Document Type
Article - Conference proceedings
Document Version
Citation
File Type
text
Language(s)
English
Rights
© 2024 Institute of Electrical and Electronics Engineers, All rights reserved.
Publication Date
01 Jan 2024
Comments
National Natural Science Foundation of China, Grant 62272328