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

Author:

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

Indexed by:

EI Scopus SCIE

Abstract:

In this work, we study a k-Cardinality Constrained Regularized Submodular Maximization (k-CCRSM) problem, in which the objective utility is expressed as the difference between a non-negative submodular and a modular function. No multiplicative approximation algorithm exists for the regularized model, and most works have focused on designing weak approximation algorithms for this problem. In this study, we consider the k-CCRSM problem in a streaming fashion, wherein the elements are assumed to be visited individually and cannot be entirely stored in memory. We propose two multipass streaming algorithms with theoretical guarantees for the above problem, wherein submodular terms are monotonic and nonmonotonic.

Keyword:

Approximation algorithms submodular optimization regularized model Boosting threshold streaming algorithms Linear programming

Author Community:

  • [ 1 ] [Gong, Qingin]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Yang, Ruiqi]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Gao, Suixiang]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:

  • [Yang, Ruiqi]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

TSINGHUA SCIENCE AND TECHNOLOGY

ISSN: 1007-0214

Year: 2024

Issue: 1

Volume: 29

Page: 76-85

6 . 6 0 0

JCR@2022

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:1286/10847249
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.