Approximation algorithms for $k$-submodular maximization subject to a knapsack constraint

Hao Xiao; Min Li; Qian Liu; Yang Zhou

REVIEW

Approximation algorithms for $k$-submodular maximization subject to a knapsack constraint

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2306.14520 v3 pith:OCCD2OCG submitted 2023-06-26 cs.DS

Hao Xiao , Qian Liu , Yang Zhou , Min Li This is my paper · ORCID

classification cs.DS

keywords approximationknapsackalgorithmapproxconstraintfracfunctionsproblem

verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments

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$.

Discussion (0). Continue with ORCID to comment.

Pith tools