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 and 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 $\frac{1-1/e}{2h+2}$ (Formula Presented) -approximation algorithm for the problem, improving the best approximation ratio $\frac{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 that depends on the problem and its typical value is 2. In addition, when $h=2$ , the algorithm approximation ratio is at least $\frac{1-1/e}{5}$ and may be as large as 1 in some special cases when $K\le 23$ , and is no less than $\frac{1-1/e}{6}$ (Formula Presented) when $K\ge24$ , compared with the current best approximation ratio $\frac{1-1/e}{7}(=\frac{1-1/e}{2h+3})$ (Formula Presented) for the problem. Finally, experimental results in the application of deploying a UAV network demonstrate that, 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 the throughput of the deployed UAV network by the proposed algorithm is up to 9.7% larger than those by the algorithms. Furthermore, the empirical approximation ratio of the proposed algorithm is between 0.7 and 0.99, which is close to the theoretical maximum value one.
Recommended Citation
Z. Wang and J. Li and H. Xue and W. Xu and W. Liang and Z. Xu and J. Peng and P. Zhou and X. Jia and S. K. Das, "Approximation Algorithm and Applications for Connected Submodular Function Maximization Problems," IEEE/ACM Transactions on Networking, Institute of Electrical and Electronics Engineers, Jan 2024.
The definitive version is available at https://doi.org/10.1109/TNET.2024.3477532
Department(s)
Computer Science
Publication Status
Early Access
Keywords and Phrases
approximation algorithms; sensor placement; submodular function maximization; UAV deployment
International Standard Serial Number (ISSN)
1558-2566; 1063-6692
Document Type
Article - Journal
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 Science Foundation, Grant ECCS-2319995