.png){kind=icon}
返回
Approximation Algorithms for the Maximum Connected Submodular Functions
.png){kind=icon}
PRE
AI
DOI：10.1007/978-981-95-0215-8_2.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
受通信网络中利用有限无人机(UAV)最大化连通覆盖的挑战启发，我们在图网络框架G=(V,E)中提出解决方案，其中V表示潜在UAV部署位置，E表示节点间的通信链路。定义效用函数f:2(V)→R+来表征覆盖效率。在有限视场(FoV)UAV的约束下，目标是在满足|S|≤K的条件下识别子集S⊂V，使得f(S)最大化且诱导子图G[S]保持连通。我们将此问题形式化为带基数约束的最大连通次模函数问题(MCSC)，并提出一个(1-e⁻¹)/(2√K⁻¹+5)-近似算法，利用新颖的树分解技术。此外，针对该问题提出一个双标准((1-e⁻¹)α/(2√K+3α), α(2))-近似算法，其中α>1为常数。对于MCSC问题的特例，即当子集足够远时次模效用呈现部分可加性，我们定义带基数约束的最大连通h跳次模函数问题(MCHSC)。当K>25h(h+1)⁻⁵时，我们给出一个比率为(1-2ε)(1-e⁻¹/(5(h+1)+1)-δ)的近似算法，其中ε、δ为小正数，h捕捉部分可加性特性。
Keyword:
Submodular optimization
Connectivity
Cardinality
Approximation algorithms
期刊
C
IF:
0
论文数:
24
被引数:
0
机构
引用论文
.png){kind=icon}
DSF-NOMA: UAV-Assisted Emergency Communication Technology in a Heterogeneous Internet of Things
PREAI
分享收藏
分享收藏分享收藏
查看更多内容