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 [B] in R+n, max{f(x):x∈[B]and∑i=1nx(i)c(i)≤1}, where n is the cardinality of a ground set N and c(·) is a cost function defined on N. Soma and Yoshida [Math. Program., 172 (2018), pp. 539-563] present a (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(n3ϵ3log3τ[log3∥B∥∞+nϵlog∥B∥∞log1ϵcmin]) time, where c_min= min _ic(i) and τ is the ratio of the maximum value of f to the minimum nonzero increase in the value of f. Besides, Ene and Nguye ˇ ~ n [arXiv:1606.08362, 2016] indirectly give a (1 - e^{- 1}- O(ϵ)) -approximation algorithm with O((1ϵ)O(1/ϵ4)nlog‖B‖∞log2(nlog‖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((1ϵ)O(1/ϵ5)·nlog1cminlog‖B‖∞), with the same approximate ratio. © The Author(s)