Regularized two-stage submodular maximization under streaming

In the problem of maximizing regularized two-stage submodular functions in streams, we assemble a family F of m functions each of which is submodular and is visited in a streaming style that an element is visited for only once. The aim is to choose a subset S of size at most l from the element stream V, so as to maximize the average maximum value of these functions restricted on S with a regularized modular term. The problem can be formally casted as max(S subset of V, vertical bar S vertical bar <= l) 1/m Sigma(m)(i=1) max(T subset of S, vertical bar T vertical bar) (<=) (k) [f(i)(T) - c(T)], where : V -> R+ is a non-negative modular function and f(i) : 2(V) -> R+, for all i is an element of {1, ..., m} is a non-negative mono- tone non-decreasing submodular function. The well-studied regularized problem of max(S subset of V,) (vertical bar S vertical bar <= k) f(S) - c(S) is exactly a special case of the above regularized two-stage submodular maximization by setting m = 1 and l = k. Although f(.) - c(.) is submodular, it is potentially negative and non-monotone and admits no constant multiplicative factor approximation. Therefore, we adopt a slightly weaker notion of approximation which constructs S such that f (S) - c(S) >= rho . f (O) - c(O) holds against optimum solution O for some rho is an element of (0, 1). Eventually, we devise a streaming algorithm by employing the distorted threshold technique, achieving a weaker approximation ratio with rho = 0.2996 for the discussed regularized two-stage model.

Automated summary

This article introduces the problem of maximizing regularized two-stage submodular functions in streams. The aim is to select a subset from an element stream in order to maximize the average maximum value of submodular functions on that subset. The article presents a streaming algorithm with a slightly weaker approximation ratio for this problem.