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

Abstract

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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\frac{1}{2}(1-\frac{1}{e})\widetilde{OPT}$</tex-math></inline-formula> guarantee, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\widetilde{OPT}$</tex-math></inline-formula> is the approximation of optimal performance. There is a gap between the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\widetilde{OPT}$</tex-math></inline-formula> and the optimal solution <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$(OPT)$</tex-math></inline-formula> . 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.