An Approximation Algorithm for the h-Hop Independently Submodular Maximization Problem and Its Applications
Authors: 
Wenzheng Xu, Hongbin Xie, Chenxi Wang, Weifa Liang, Xiaohua Jia, Zichuan Xu, Pan Zhou, Weigang Wu, Xiang ChenAuthors Info & Claims
Pages 1216 - 1229
Abstract
This study is motivated by the maximum connected coverage problem (MCCP), which is to deploy a connected UAV network with given <inline-formula> <tex-math notation="LaTeX">$K$ </tex-math></inline-formula> 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 <inline-formula> <tex-math notation="LaTeX">$h$ </tex-math></inline-formula>-hop independently submodular maximization problem, where the MCCP problem is one of its special cases with <inline-formula> <tex-math notation="LaTeX">$h=4$ </tex-math></inline-formula>. We propose a <inline-formula> <tex-math notation="LaTeX">$\frac {1-1/e}{2h+3}$ </tex-math></inline-formula>-approximation algorithm for the <inline-formula> <tex-math notation="LaTeX">$h$ </tex-math></inline-formula>-hop independently submodular maximization problem, where <inline-formula> <tex-math notation="LaTeX">$e$ </tex-math></inline-formula> is the base of the natural logarithm. Then, one direct result is a <inline-formula> <tex-math notation="LaTeX">$\frac {1-1/e}{11}$ </tex-math></inline-formula>-approximate solution to the MCCP problem with <inline-formula> <tex-math notation="LaTeX">$h=4$ </tex-math></inline-formula>, which significantly improves its currently best <inline-formula> <tex-math notation="LaTeX">$\frac {1-1/e}{32}$ </tex-math></inline-formula>-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.
References
[1]
A. Al-Hourani, S. Kandeepan, and S. Lardner, “Optimal LAP altitude for maximum coverage,” IEEE Wireless Commun. Lett., vol. 3, no. 6, pp. 569–572, Dec. 2014.
[2]
K. Avrachenkov, P. Basu, G. Neglia, B. Ribeiro, and D. Towsley, “Online myopic network covering,” 2012, arXiv:1212.5035.
[3]
I. Bor-Yaliniz and H. Yanikomeroglu, “The new frontier in RAN heterogeneity: Multi-tier drone-cells,” IEEE Commun. Mag., vol. 54, no. 11, pp. 48–55, Nov. 2016.
[4]
N. Buchbinder and M. Feldman, “Deterministic algorithms for submodular maximization problems,” ACM Trans. Algorithms, vol. 14, no. 3, p. 32, 2018.
[5]
N. Buchbinder, M. Feldman, and M. Garg, “Deterministic (1/2 + ε)-approximation for submodular maximization over a matroid,” in Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), 2019, pp. 241–254.
[6]
N. Buchbinder, M. Feldman, J. Seffi, and R. Schwartz, “A tight linear time (1/2)-approximation for unconstrained submodular maximization,” SIAM J. Comput., vol. 44, no. 5, pp. 1384–1402, Jan. 2015.
[7]
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, “Maximizing a submodular set function subject to a matroid constraint (extended abstract),” in Proc. Int. Conf. Integer Program. Combinat. Optim. (IPCO), 2007, pp. 182–196.
[8]
S. Chandrasekharanet al., “Designing and implementing future aerial communication networks,” IEEE Commun. Mag., vol. 54, no. 5, pp. 26–34, May 2016.
[9]
L. Denget al., “Approximation algorithms for min-max cycle cover problems with neighborhoods,” IEEE/ACM Trans. Netw., vol. 28, no. 4, pp. 1845–1858, Aug. 2020.
[10]
Y. Filmus and J. Ward, “A tight combinatorial algorithm for submodular maximization subject to a matroid constraint,” in Proc. IEEE 53rd Annu. Symp. Found. Comput. Sci., Oct. 2012, pp. 659–668.
[11]
M. L. Fisher, G. L. Nemhausert, and L. A. Wolsey, “An analysis of the approximations for maximizing submodular set functions—II,” Math. Program. Study, vol. 8, pp. 73–87, Jan. 1978.
[12]
N. Garg, “Saving an epsilon: A 2-approximation for the k-MST problem in graphs,” in Proc. 37th Anuu. ACM Symp. Theory Comput. (STOC), 2005, pp. 396–402.
[13]
J. Gong, T.-H. Chang, C. Shen, and X. Chen, “Flight time minimization of UAV for data collection over wireless sensor networks,” IEEE J. Sel. Areas Commun., vol. 36, no. 9, pp. 1942–1954, Sep. 2018.
[14]
Q. Guoet al., “Minimizing the longest tour time among a fleet of UAVs for disaster area surveillance,” IEEE Trans. Mobile Comput., vol. 21, no. 7, pp. 2451–2465, Jul. 2022.
[15]
L. Huang, J. Li, and Q. Shi, “Approximation algorithms for the connected sensor cover problem,” in Proc. 21st Int. Conf. Comput. Combinatorics (COCOON), 2015, pp. 183–196.
[16]
D. S. Johnson, M. Minkoff, and S. Phillips, “The prize collecting Steiner tree problem: Theory and practice,” in Proc. 11th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA), 2000, pp. 760–769.
[17]
S. Khuller, M. Purohit, and K. K. Sarpatwar, “Analyzing the optimal neighborhood: Algorithms for budgeted and partial connected dominating set problems,” in Proc. 25th Annu. ACM-SIAM Symp. Discrete Algorithms, Jan. 2014, pp. 1702–1713.
[18]
S. Khuller, M. Purohit, and K. K. Sarpatwar, “Analyzing the optimal neighborhood: Algorithms for partial and budgeted connected dominating set problems,” SIAM J. Discrete Math., vol. 34, no. 1, pp. 251–270, Jan. 2020.
[19]
A. Kulik, H. Shachnai, and T. Tamir, “Maximizing submodular set functions subject to multiple linear constraints,” in Proc. 20th Annu. ACM-SIAM Symp. Discrete Algorithms, Jan. 2009, pp. 545–554.
[20]
T.-W. Kuo, K. C.-J. Lin, and M.-J. Tsai, “Maximizing submodular set function with connectivity constraint: Theory and application to networks,” IEEE/ACM Trans. Netw., vol. 23, no. 2, pp. 533–546, Apr. 2015.
[21]
I. Lamprou, I. Sigalas, and V. Zissimopoulos, “Improved budgeted connected domination and budgeted edge-vertex domination,” Theor. Comput. Sci., vol. 858, pp. 1–12, Feb. 2021.
[22]
J. Lee, M. Sviridenko, and J. Vondrák, “Submodular maximization over multiple matroids via generalized exchange properties,” in Proc. 12th Int. Workshop Approximation Algorithms Combinat. Optim., 13th Int. Workshop Randomization Approximation Tech. Comput. Sci. (APPROX-RANDOM), 2009, pp. 244–257.
[23]
C. H. Liu, Z. Chen, J. Tang, J. Xu, and C. Piao, “Energy-efficient UAV control for effective and fair communication coverage: A deep reinforcement learning approach,” IEEE J. Sel. Areas Commun., vol. 36, no. 9, pp. 2059–2070, Sep. 2018.
[24]
Y. Liu and W. Liang, “Approximate coverage in wireless sensor networks,” in Proc. 30th Annu. IEEE Conf. Local Comput. Netw. (LCN), Nov. 2005, pp. 68–75.
[25]
M. Moradi, K. Sundaresan, E. Chai, S. Rangarajan, and Z. M. Mao, “SkyCore: Moving core to the edge for untethered and reliable UAV-based LTE networks,” in Proc. 24th Annu. Int. Conf. Mobile Comput. Netw., Oct. 2018, pp. 35–49.
[26]
G. Nemhauser and L. A. Wolsey, “An analysis of the approximations for maximizing submodular set functions—I,” Math. Program., vol. 14, no. 1, pp. 265–294, 1978.
[27]
W. Shiet al., “Multi-drone 3-D trajectory planning and scheduling in drone-assisted radio access networks,” IEEE Trans. Veh. Technol., vol. 68, no. 8, pp. 8145–8158, Aug. 2019.
[28]
C. Song, T. Koren, P. Wang, and A.-L. Barabási, “Modelling the scaling properties of human mobility,” Nature Phys., vol. 6, no. 10, pp. 818–823, Sep. 2010.
[29]
M. Sviridenko, “A note on maximizing a submodular set function subject to a knapsack constraint,” Oper. Res. Lett., vol. 32, no. 1, pp. 41–43, 2004.
[30]
W. Xu, T. Li, W. Liang, J. X. Yu, N. Yang, and S. Gao, “Identifying structural hole spanners to maximally block information propagation,” Inf. Sci., vol. 505, pp. 100–126, Dec. 2019.
[31]
W. Xu, W. Liang, and X. Lin, “Approximation algorithms for min-max cycle cover problems,” IEEE Trans. Comput., vol. 64, no. 3, pp. 600–613, Mar. 2015.
[32]
W. Xu, W. Liang, X. Lin, and J. X. Yu, “Finding top-k influential users in social networks under the structural diversity model,” Inf. Sci., vols. 355–356, pp. 110–126, Aug. 2016.
[33]
W. Xuet al., “Approximation algorithms for the generalized team orienteering problem and its applications,” IEEE/ACM Trans. Netw., vol. 29, no. 1, pp. 176–189, Feb. 2021.
[34]
W. Xu, M. Rezvani, W. Liang, J. X. Yu, and C. Liu, “Efficient algorithms for the identification of top-k structural hole spanners in large social networks,” IEEE Trans. Knowl. Data Eng., vol. 29, no. 5, pp. 1017–1030, May 2017.
[35]
W. Xuet al., “Throughput maximization of UAV networks,” IEEE/ACM Trans. Netw., vol. 30, no. 2, pp. 881–895, Apr. 2022.
[36]
W. Xuet al., “Minimizing the deployment cost of UAVs for delay-sensitive data collection in IoT networks,” IEEE/ACM Trans. Netw., vol. 30, no. 2, pp. 812–825, Apr. 2022.
[37]
W. Xuet al., “Approximation algorithms for the team orienteering problem,” in Proc. IEEE Conf. Comput. Commun. (IEEE INFOCOM), Jul. 2020, pp. 1389–1398.
[38]
P. Yang, X. Cao, X. Xi, W. Du, Z. Xiao, and D. Wu, “Three-dimensional continuous movement control of drone cells for energy-efficient communication coverage,” IEEE Trans. Veh. Technol., vol. 68, no. 7, pp. 6535–6546, Jul. 2019.
[39]
N. Yu, H. Dai, A. X. Liu, and B. Tian, “Placement of connected wireless chargers,” in Proc. IEEE Conf. Comput. Commun. (IEEE INFOCOM), Apr. 2018, pp. 387–395.
[40]
N. Yu, H. Dai, G. Chen, A. X. Liu, B. Tian, and T. He, “Connectivity-constrained placement of wireless chargers,” IEEE Trans. Mobile Comput., vol. 20, no. 3, pp. 909–927, Mar. 2021.
[41]
Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory optimization,” IEEE Trans. Wireless Commun., vol. 16, no. 6, pp. 3747–3760, Jun. 2017.
[42]
J. Zhanget al., “Minimizing the number of deployed UAVs for delay-bounded data collection of IoT devices,” in Proc. 40th IEEE Int. Conf. Comput. Commun. (INFOCOM), May 2021, pp. 1–10.
[43]
H. Zhao, H. Wang, W. Wu, and J. Wei, “Deployment algorithms for UAV airborne networks toward on-demand coverage,” IEEE J. Sel. Areas Commun., vol. 36, no. 9, pp. 2015–2031, Sep. 2018.
Index Terms
- An Approximation Algorithm for the h-Hop Independently Submodular Maximization Problem and Its Applications
Index terms have been assigned to the content through auto-classification.
Recommendations
Maximizing h-hop Independently Submodular Functions Under Connectivity Constraint
IEEE INFOCOM 2022 - IEEE Conference on Computer CommunicationsThis 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 ...
Symmetry and Approximability of Submodular Maximization Problems
A number of recent results on optimization problems involving submodular functions have made use of the multilinear relaxation of the problem. These results hold typically in the value oracle model, where the objective function is accessible via a black box ...
Discrete Stochastic Submodular Maximization: Adaptive vs. Non-adaptive vs. Offline
CIAC 2015: Proceedings of the 9th International Conference on Algorithms and Complexity - Volume 9079We consider the problem of stochastic monotone submodular function maximization, subject to constraints. We give results on adaptivity gaps, and on the gap between the optimal offline and online solutions. We present a procedure that transforms a ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1558-2566 © 2022 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Press
Publication History
Published: 05 October 2022
Published in TON Volume 31, Issue 3
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 8Total Downloads
- Downloads (Last 12 months)8
- Downloads (Last 6 weeks)1
Reflects downloads up to 13 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in