Approximation algorithms for k-submodular maximization subject to a knapsack constraint
Reviewed by Pith T0 review T1 audit T2 compute T3 formal T4 kernel pith:OCCD2OCGrecord.jsonopen to challenge →
classification
cs.DS
keywords
approximationknapsackalgorithmapproxconstraintfracfunctionsproblem
read the original abstract
In this paper, we study the problem of maximizing $k$-submodular functions subject to a knapsack constraint. For monotone objective functions, we present a $\frac{1}{2}(1-e^{-2})\approx 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 $\frac{1}{3}(1-e^{-3})\approx 0.317$.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.