Approximation algorithms for k-submodular maximization subject to a knapsack constraint
share
In this paper, we study the problem of maximizing k-submodular functions subject to a knapsack constraint. For monotone objective functions, we present a 1/2(1-e^-2)≈ 0.432 greedy approximation algorithm. For the non-monotone case, we are the first to consider the knapsack problem and provide a greedy-type combinatorial algorithm with approximation ratio 1/3(1-e^-3)≈ 0.317.
READ FULL TEXT