Fast algorithms combining threshold-decreasing and greedy methods for maximizing constraint k-submodular functions

In recent years, there has been significant research directed toward the maximization of Formula: see text-submodular functions, owing to their wide-ranging applications in fields such as social networks, sensor placement, and various other domains. The utilization of the greedy method and randomized techniques is prevalent for the design of algorithms that offer favorable performance guarantees for such problems. However, these approaches adopt a single-item selection strategy at each iteration, leading to high query complexity. The Threshold-Decreasing Algorithm is conceptualized to address this issue by choosing multiple items using a predefined threshold value, and in case no items remain, the threshold is decremented by a specified factor. This approach effectively reduces complexity. In this paper, we merge the principles of the threshold-decreasing and greedy methods to enhance the complexity of constrained Formula: see text-submodular maximization problems, thereby achieving near-optimal approximation ratios.