Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
SCIENCE CHINA-INFORMATION SCIENCES
ISSN: 1674-733X
Year: 2022
Issue: 4
Volume: 65
8 . 8
JCR@2022
8 . 8 0 0
JCR@2022
ESI Discipline: COMPUTER SCIENCE;
ESI HC Threshold:46
JCR Journal Grade:1
CAS Journal Grade:2
Cited Count:
WoS CC Cited Count: 3
SCOPUS Cited Count: 4
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 1
Affiliated Colleges: