4.6 Article

Regularized two-stage submodular maximization under streaming

Journal

SCIENCE CHINA-INFORMATION SCIENCES
Volume 65, Issue 4, Pages -

Publisher

SCIENCE PRESS
DOI: 10.1007/s11432-020-3420-9

Keywords

submodular maximization; streaming model; two-stage; threshold technique; approximation algorithms

Funding

  1. National Natural Science Foundation of China [12101587, 12131003, 61772005, 11871081]
  2. China Postdoctoral Science Foundation [2021M703167]
  3. Fundamental Research Funds for the Central Universities [EIE40108X2]
  4. Beijing Natural Science Foundation Project [Z200002]
  5. Outstanding Youth Innovation Team Project for Universities of Shandong Province [2020KJN008]

Ask authors/readers for more resources

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.
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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.6
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available