An Approximation Algorithm for the h-Hop Independently Submodular Maximization Problem and Its Applications

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

View graph of relations


  • Wenzheng Xu
  • Hongbin Xie
  • Chenxi Wang
  • Zichuan Xu
  • Pan Zhou
  • Weigang Wu
  • Xiang Chen

Related Research Unit(s)


Original languageEnglish
Journal / PublicationIEEE - ACM Transactions on Networking
Online published5 Oct 2022
Publication statusOnline published - 5 Oct 2022


This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given Κ 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 (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 (1-1/e)11 -approximate solution to the MCCP problem with h = 4, which significantly improves its currently best (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.

Research Area(s)

  • UAV communication networks, maximum connected coverage problem, connected sensor coverage problem, submodular function maximization, approximation algorithms, COMMUNICATION, NETWORKS