• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Gong, Qinqin (Gong, Qinqin.) | Gao, Suixiang (Gao, Suixiang.) | Wang, Fengmin (Wang, Fengmin.) | Yang, Ruiqi (Yang, Ruiqi.)

Indexed by:

CPCI-S EI Scopus

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:

Stream model Submodular maximization Multi-pass Streaming algorithms Threshold-based

Author Community:

  • [ 1 ] [Gong, Qinqin]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 2 ] [Gao, Suixiang]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 3 ] [Yang, Ruiqi]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 4 ] [Wang, Fengmin]Beijing Jinghang Res Inst Comp & Commun, Beijing 100074, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Related Article:

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:

Online/Total:341/10642428
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.