• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

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

收录:

EI Scopus SCIE

摘要:

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.

关键词:

approximation algorithm submodular maximization streaming model threshold technique

作者机构:

  • [ 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

通讯作者信息:

查看成果更多字段

相关关键词:

相关文章:

来源 :

TSINGHUA SCIENCE AND TECHNOLOGY

ISSN: 1007-0214

年份: 2023

期: 5

卷: 28

页码: 906-915

6 . 6 0 0

JCR@2022

ESI学科: COMPUTER SCIENCE;

ESI高被引阀值:19

被引次数:

WoS核心集被引频次:

SCOPUS被引频次: 2

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 0

归属院系:

在线人数/总访问数:308/4974561
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司