A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice

Maximizing non-monotone submodular functions is one of the most important problems in submodular optimization. Let $$\mathbf {B}=(B_1, B_2,\ldots , B_n)\in {\mathbb {Z}}_+^n$$B=(B1,B2,…,Bn)∈Z+n be an integer vector and $$[\mathbf { B}]=\{(x_1,\dots ,x_n) \in {\mathbb {Z}}_+^n: 0\le x_k \le B_k, \forall 1\le k\le n\}$$[B]={(x1,⋯,xn)∈Z+n:0≤xk≤Bk,∀1≤k≤n} be the set of all non-negative integer vectors not greater than $$\mathbf {B}$$B. A function $$f:[\mathbf { B}] \rightarrow {\mathbb {R}}$$f:[B]→R is said to be weak-submodular if $$f(\mathbf {x}+\delta \mathbf {1}_k)-f(\mathbf {x})\ge f(\mathbf {y}+\delta \mathbf {1}_k)-f(\mathbf {y})$$f(x+δ1k)-f(x)≥f(y+δ1k)-f(y) for any $$k\in \{1,\dots ,n\}$$k∈{1,⋯,n}, any pair of $$\mathbf {x}, \mathbf {y}\in [\mathbf { B}]$$x,y∈[B] such that $$\mathbf {x}\le \mathbf {y}$$x≤y and $$x_k =y_k$$xk=yk, and any $$\delta \in {\mathbb {Z}}_+$$δ∈Z+ satisfying $$\mathbf {y}+\delta \mathbf {1}_k\in [\mathbf { B}]$$y+δ1k∈[B]. Here $$\mathbf {1}_k$$1k is the vector with the kth component equal to 1 and each of the others equals to 0. In this paper we consider the problem of maximizing a non-monotone and non-negative weak-submodular function on the bounded integer lattice without any constraint. We present an randomized algorithm with an approximation guarantee $$\frac{1}{2}$$12 for the problem.