Approximation Algorithm and Applications for Connected Submodular Function Maximization Problems

doi:10.1109/TNET.2024.3477532

2025-02-01

PRE

DOI：10.1109/TNET.2024.3477532

原文链接

原文求助

摘要

En 中文

In this paper, we study a connected submodular function maximization problem, which arises from many applications including deploying UAV networks to serve users and placing sensors to cover Points of Interest (PoIs). Specifically, given a budget K , the problem is to find a subset S with K nodes from a graph G , so that a given submodular function f(S) on S is maximized and the induced subgraph G[S] by the nodes in S is connected, where the submodular function f can be used to model many practical application problems, such as the number of users within different service areas of the deployed UAVs in S , the sum of data rates of users served by the UAVs, the number of covered PoIs by placed sensors, etc. We then propose a novel 1-1/e/2h+2 -approximation algorithm for the problem, improving the best approximation ratio 1-1/e/2h+3 for the problem so far, through estimating a novel upper bound on the problem and designing a smart graph decomposition technique, where e is the base of the natural logarithm, h is a parameter that depends on the problem and its typical value is 2. In addition, when h=2 , the algorithm approximation ratio is at least 1-1/e/5 and may be as large as 1 in some special cases when K <= 23 , and is no less than 1-1/e/6 when K >= 24 , compared with the current best approximation ratio 1-1/e/7(=1-1/e/2h+3) for the problem. Finally, experimental results in the application of deploying a UAV network demonstrate that, the number of users within the service area of the deployed UAV network by the proposed algorithm is up to 7.5% larger than those by existing algorithms, and the throughput of the deployed UAV network by the proposed algorithm is up to 9.7% larger than those by the algorithms. Furthermore, the empirical approximation ratio of the proposed algorithm is between 0.7 and 0.99, which is close to the theoretical maximum value one.

Keyword:

Sensors

Autonomous aerial vehicles

Approximation algorithms

Disasters

Wireless sensor networks

Capacitive sensors

Water pollution

Social networking (online)

Contamination

Computer science

UAV deployment