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

Author:

Yang, Ruiqi (Yang, Ruiqi.) | Gao, Suixiang (Gao, Suixiang.) | Han, Lu (Han, Lu.) | Li, Gaidi (Li, Gaidi.) | Zhao, Zhongrui (Zhao, Zhongrui.)

Indexed by:

EI Scopus SCIE

Abstract:

The paper proposes the optimization problem of maximizing the sum of suBmodular and suPermodular (BP) functions with partial monotonicity under a streaming fashion. In this model, elements are randomly released from the stream and the utility is encoded by the sum of partial monotone suBmodular and suPermodular functions. The goal is to determine whether a subset from the stream of size bounded by parameter k subject to the summarized utility is as large as possible. In this work, a threshold-based streaming algorithm is presented for the BP maximization that attains a((1 - kappa)/(2 - kappa) - O(epsilon))-approximation with O(1/epsilon(4) log(3) (1/epsilon) log ((2 - kappa) k/ (1 - kappa)(2))) memory complexity, where kappa denotes the parameter of supermodularity ratio. We further consider a more general model with fair constraints and present a greedy-based algorithm that obtains the same approximation. We finally investigate this fair model under the streaming fashion and provide a ((1 - kappa)(4) / (2 - 2 kappa + kappa(2))(2) - O(epsilon))-approximation algorithm.

Keyword:

approximation algorithm submodular maximization streaming model threshold technique

Author Community:

  • [ 1 ] [Yang, Ruiqi]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Li, Gaidi]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Zhao, Zhongrui]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 4 ] [Gao, Suixiang]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China
  • [ 5 ] [Han, Lu]Beijing Univ Posts & Telecommun, Sch Sci, Beijing 100876, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Related Article:

Source :

TSINGHUA SCIENCE AND TECHNOLOGY

ISSN: 1007-0214

Year: 2023

Issue: 5

Volume: 28

Page: 906-915

6 . 6 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:19

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: 0

Affiliated Colleges:

Online/Total:1702/10901067
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.