Streaming algorithms for Budgeted k-Submodular Maximization problem
share
Stimulated by practical applications arising from viral marketing. This paper investigates a novel Budgeted k-Submodular Maximization problem defined as follows: Given a finite set V, a budget B and a k-submodular function f: (k+1)^V ↦ℝ_+, the problem asks to find a solution =(S_1, S_2, …, S_k), each element e ∈ V has a cost c_i(e) to be put into i-th set S_i, with the total cost of s does not exceed B so that f() is maximized. To address this problem, we propose two streaming algorithms that provide approximation guarantees for the problem. In particular, in the case of each element e has the same cost for all i-th sets, we propose a deterministic streaming algorithm which provides an approximation ratio of 1/4-ϵ when f is monotone and 1/5-ϵ when f is non-monotone. For the general case, we propose a random streaming algorithm that provides an approximation ratio of min{α/2, (1-α)k/(1+β)k-β}-ϵ when f is monotone and min{α/2, (1-α)k/(1+2β)k-2β}-ϵ when f is non-monotone in expectation, where β=max_e∈ V, i , j ∈ [k], i≠ jc_i(e)/c_j(e) and ϵ, α are fixed inputs.
READ FULL TEXT