Two-Stage Submodular Maximization Under Knapsack Problem

Two-stage submodular maximization problem under cardinality constraint has been widely studied in machine learning and combinatorial optimization. In this paper, we consider knapsack constraint. In this problem, we give $n$ articles and $m$ categories, and the goal is to select a subset of articles that can maximize the function $F(S)$. Function $F(S)$ consists of $m$ monotone submodular functions $f_j$, $j=1,2,\dots ,m$, and each $f_j$ measures the similarity of each article in category $j$. We present a constant-approximation algorithm for this problem.