2023/11/30 by Zhang, Hongyang, Wenchang Luo, Luo, Wenchang
Computer Science · Engineering · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cryptography and Data Security #FOS: Mathematics #Infrastructure Maintenance and Monitoring
paper · pdf · doi:10.48550/arxiv.2311.18239
openalex publication_date 2023/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A k-submodular function is a generalization of the submodular set function. Many practical applications can be modeled as maximizing a k-submodular function, such as multi-cooperative games, sensor placement with k type sensors, influence maximization with k topics, and feature selection with k partitions. In this paper, we provide a unified continuous greedy algorithm for k-submodular maximization problem under a down-monotone constraint. Our technique involves relaxing the discrete variables in a continuous space by using the multilinear extension of k-submodular function to find a fractional solution, and then rounding it to obtain the feasible solution. Our proposed algorithm runs in polynomial time and can be applied to both the non-monotone and monotone cases. When the objective function is non-monotone, our algorithm achieves an approximation ratio of (1/e-o(1)); for a monotone k-submodular objective function, it achieves an approximation ratio of (1-1/e-o(1)).