.png){kind=icon}
.png){kind=icon}
Return
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}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Motivated by the challenge of maximizing connected coverage with limited UAVs in communication networks, we address the problem within a graph network framework G = (V, E), where.V represents potential UAV deployment positions and.E denotes communication links between nodes. A utility function f : 2(V)-> R+ is defined to characterize coverage efficiency. Under the constraint of limited field-of-view (FoV) UAVs, the objective is to identify a subset S subset of V with |S| <= K that maximizes f(S) while ensuring the induced subgraph G[S] remains connected. We formulate this as the Maximum Connected Submodular function with Cardinality constraint (MCSC) problem and propose a (1- e-1)/(2 root K-1+5)-approximation algorithm, leveraging a novel tree decomposition technique. Additionally, we present a bicriteria ( ((1-e-1) alpha)/(2 root K+3 alpha), alpha(2)) approximation algorithm for the problem, where alpha > 1 is a constant. For a special case of the MCSC problem, where the submodular utility exhibits partial additivity when subsets are sufficiently far apart, we define the Maximum Connected h-Hop Submodular function with a Cardinality constraint (MCHSC) problem. We provide an approximation algorithm with a ratio of (1- 2 epsilon) (1-e(-1) /(5(h+1)+1) - delta) when K > 25h(h+1)- 5, where epsilon,delta are small positive constants and.h captures the partial additivity property.
Keywords:
Submodular optimization
Connectivity
Cardinality
Approximation algorithms
Journal
C
IF:
0
Papers:
24
Citations:
0