Greedy+Singleton: An efficient approximation algorithm for k-submodular knapsack maximization

A k-submodular function takes k distinct, non-overlapping subsets of a ground set as input and outputs a value. It is a generalization of the well-known submodular function, which is the case when k = 1 and takes a single subset as input. We study the problem of maximizing a non-negative k-submodular function under a knapsack constraint. Greedy+Singleton is an algorithm that chooses the better solution between the fully greedy solution and the best single-element solution, with query complexity and running time of O ( n 2 k ). We show that Greedy+Singleton has an approximation ratio of 0. 273 for monotone functions, which improves the previous analysis of 0. 158 in the literature. Moreover, we give the first analysis of Greedy+Singleton for non-monotone k-submodular functions, and prove an approximation ratio of 0. 219.

Authors

• Zhongzheng Tang
• Jingwen Chen
• Chenhao Wang Beijing Normal University-Zhuhai & IRADS, Beijing Normal-Hong Kong Baptist University

Keywords

• Submodularity
• Approximation algorithm
• Greedy algorithm
• Knapsack