次模集函数
计算机科学
对数
约束(计算机辅助设计)
最大化
近似算法
组合数学
数学优化
算法
数学
数学分析
几何学
作者
Wenzheng Xu,Dezhong Peng,Weifa Liang,Xiaohua Jia,Zichuan Xu,Pan Zhou,Weigang Wu,Xiang Chen
标识
DOI:10.1109/infocom48880.2022.9796957
摘要
This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given K UAVs in the top of a disaster area such that the number of users served by the UAVs is maximized. The deployed UAV network must be connected, since the received data by a UAV from its served users need to be sent to the Internet through relays of other UAVs. Motivated by this application, in this paper we study a more generalized problem – the h-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with h = 4. We propose a $\frac{{1 - 1/e}}{{2h + 3}}$-approximation algorithm for the h-hop independently submodular maximization problem, where e is the base of the natural logarithm. Then, one direct result is a $\frac{{1 - 1/e}}{{11}}$-approximate solution to the MCCP problem with h = 4, which significantly improves its currently best $\frac{{1 - 1/e}}{{32}}$-approximate solution. We finally evaluate the performance of the proposed algorithm for the MCCP problem in the application of deploying UAV networks, and experimental results show that the number of users served by deployed UAVs delivered by the proposed algorithm is up to 12.5% larger than those by existing algorithms.
科研通智能强力驱动
Strongly Powered by AbleSci AI