Improvement of Submodular Maximization Problems With Routing Constraints via Submodularity and Fourier Sparsity

Pao Te Lin, Kuo Shih Tseng

研究成果: 雜誌貢獻期刊論文同行評審

1 引文 斯高帕斯(Scopus)

摘要

Various robotic problems (e.g., map exploration, environmental monitoring and spatial search) can be formulated as submodular maximization problems with routing constraints. These problems involve two NP-hard problems, maximal coverage and traveling salesman problems. The generalized cost-benefit algorithm (GCB) is able to solve this problem with a 1 2 (1-1 e)\widetilde OPT guarantee, where OPT is the approximation of optimal performance. There is a gap between the OPT and the optimal solution (OPT). In this research, the proposed algorithms, Tree-Structured Fourier Supports Set (TS-FSS), utilize the submodularity and sparsity of routing trees to boost GCB performance. The theorems show that the proposed algorithms have a higher optimum bound than GCB. The experiments demonstrate that the proposed approach outperforms benchmark approaches.

原文???core.languages.en_GB???
頁(從 - 到)1927-1934
頁數8
期刊IEEE Robotics and Automation Letters
8
發行號4
DOIs
出版狀態已出版 - 1 4月 2023

指紋

深入研究「Improvement of Submodular Maximization Problems With Routing Constraints via Submodularity and Fourier Sparsity」主題。共同形成了獨特的指紋。

引用此