Monotone submodular maximization over the bounded integer lattice with cardinality constraints

We consider the problem of maximizing monotone submodular function over the bounded integer lattice with a cardinality constraint. Function f: ℤ₊^E → R₊ is submodular over integer lattice if f(x) + f(y) ≥ f(x ∨ y) + f(x ∧ y), ∀ x,y ∈ ℤ₊^E, where ∨ and ∧ represent elementwise maximum and minimum, respectively. Let B ∈ ℤ₊^E, and k ∈ ℤ₊, we study the problem of maximizing submodular function f(x) with constraints 0 ≤x ≤B and x(E) ≤ k. A random greedy (1 -1/e)-approximation algorithm and a deterministic 1 e-approximation algorithm are proposed in this paper. Both algorithms work in value oracle model. In the random greedy algorithm, we assume the monotone submodular function satisfies diminishing return property, which is not an equivalent definition of submodularity on integer lattice. Additionally, our random greedy algorithm makes Ο((|E| + 1)· k) value oracle queries and deterministic algorithm makes Ο(|E|· B Ο · k³) value oracle queries.