Indexed by:
Abstract:
In this paper, we consider a problem of maximizing regularized submodular functions with a k-cardinality constraint under streaming fashion. In the model, the utility function f(.) = g(.)-l(.) is expressed as the difference between a non-negative monotone non-decreasing submodular function g and a non-negative modular function l. In addition, the elements are revealed in a streaming setting, that is to say, an element is visited in one time slot. The problem asks to find a subset of size at most k such that the regularized utility value is maximized. Most of the existing algorithms for the submodular maximization heavily rely on the non-negativity assumption of the utility function, which may not be applicable for our regularized scenario. Indeed, determining if the maximum is positive or not is NP-hard, which implies that no multiplicative factor approximation is existed for this problem. To circumvent this challenge, several works paid attention to more meaningful guarantees by introducing a slightly weaker notion of approximation, and any developed algorithm is aim to construct a solution S satisfying f(S) >= rho . g(OPT) - l(OPT) for some rho > 0. In this work, assume there is a weak.-approximation for the k-cardinality constrained regularized submodular maximization, we develop Distorted-Threshold-Streaming, a multi-pass bicriteria algorithm for the streaming regularized submodular maximization with the k-cardinality constraint (SRSMCC), which produces a (rho/lambda, 1/lambda)-bicriteria approximation bymaking over O(log(lambda/rho)/epsilon) passes, consuming O(k) memory and using O(log(lambda/rho)/epsilon) queries per element, where lambda = 2-(2 rho+2)/(3+root 5-4 rho)/(3+root 5-4 rho)/(2 rho+2)-1 and any accuracy parameter epsilon > 0.
Keyword:
Reprint Author's Address:
Email:
Source :
COMBINATORIAL OPTIMIZATION AND APPLICATIONS, COCOA 2021
ISSN: 0302-9743
Year: 2021
Volume: 13135
Page: 701-711
Cited Count:
WoS CC Cited Count: 3
SCOPUS Cited Count: 3
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 8
Affiliated Colleges: