A fast and deterministic algorithm for Knapsack-constrained monotone DR-submodular maximization over an integer lattice

We consider a knapsack-constrained maximization problem of a nonnegative monotone DR-submodular function f over a bounded integer lattice $$[\varvec{B}]$$ [ B ] in $${\mathbb {R}}_+^n$$ R + n , $$\max \{f({\varvec{x}}): {\varvec{x}}\in [\varvec{B}] \text {~and~} \sum _{i=1}^n {\varvec{x}}(i)c(i)\le 1\}$$ max { f ( x ) : x ∈ [ B ] and ∑ i = 1 n x ( i ) c ( i ) ≤ 1 } , where n is the cardinality of a ground set N and $$c(\cdot )$$ c ( · ) is a cost function defined on N. Soma and Yoshida [Math. Program., 172 (2018), pp. 539-563] present a $$(1-e^{-1}-O(\epsilon ))$$ ( 1 - e - 1 - O ( ϵ ) ) -approximation algorithm for this problem by combining threshold greedy algorithm with partial element enumeration technique. Although the approximation ratio is almost tight, their algorithm runs in $$O(\frac{n^3}{\epsilon ^3}\log ^3 \tau [\log ^3 \left\| \varvec{B}\right\| _\infty + \frac{n}{\epsilon }\log \left\| \varvec{B}\right\| _\infty \log \frac{1}{\epsilon c_{\min }}])$$ O ( n 3 ϵ 3 log 3 τ [ log 3 B ∞ + n ϵ log B ∞ log 1 ϵ c min ] ) time, where $$c_{\min }=\min _i c(i)$$ c min = min i c ( i ) and $$\tau $$ τ is the ratio of the maximum value of f to the minimum nonzero increase in the value of f. Besides, Ene and Nguy $$\tilde{\check{\text {e}}}$$ e ˇ ~ n [ arXiv:1606.08362 , 2016] indirectly give a $$(1-e^{-1}-O(\epsilon ))$$ ( 1 - e - 1 - O ( ϵ ) ) -approximation algorithm with $$O({(\frac{1}{\epsilon })}^{ O(1/\epsilon ^4)}n \log {\Vert \varvec{B}\Vert }_\infty \log ^2{(n \log {\Vert \varvec{B}\Vert }_\infty )})$$ O ( ( 1 ϵ ) O ( 1 / ϵ 4 ) n log ‖ B ‖ ∞ log 2 ( n log ‖ B ‖ ∞ ) ) time. But their algorithm is random. In this paper, we make full use of the DR-submodularity over a bounded integer lattice, carry forward the greedy idea in the continuous process and provide a simple deterministic rounding method so as to obtain a feasible solution of the original problem without loss of objective value. We present a deterministic algorithm and theoretically reduce its running time to a new record, $$O\big ((\frac{1}{\epsilon })^{O({1}/{\epsilon ^5})} \cdot n \log \frac{1}{c_{\min }} \log {\Vert \varvec{B}\Vert _\infty }\big )$$ O ( ( 1 ϵ ) O ( 1 / ϵ 5 ) · n log 1 c min log ‖ B ‖ ∞ ) , with the same approximate ratio.