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

作者:

Zhang, Zhenning (Zhang, Zhenning.) | Guo, Longkun (Guo, Longkun.) | Wang, Linyang (Wang, Linyang.) | Zou, Juan (Zou, Juan.)

收录:

EI Scopus SCIE

摘要:

In the article, we devise streaming algorithms for maximization of a monotone submodular function subject to a cardinality constraint on the integer lattice. Based on the observation that lattice submodularity is not equivalent to diminishing return submodularity on the integer lattice but rather a weaker condition, we propose a one-pass streaming algorithm with a modified binary search as subroutine of each step. Finally, we show that the algorithm is with approximation ratio 1/2-epsilon, memory complexity O(epsilon-1klogk), and per-element query complexity O(epsilon-2log2k).

关键词:

cardinality integer lattice lattice submodular memory complexity streaming algorithm

作者机构:

  • [ 1 ] [Zhang, Zhenning]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing, Peoples R China
  • [ 2 ] [Wang, Linyang]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing, Peoples R China
  • [ 3 ] [Guo, Longkun]Fuzhou Univ, Coll Math & Comp Sci, Fuzhou, Peoples R China
  • [ 4 ] [Guo, Longkun]Qilu Univ Technol, Sch Comp Sci, Room 420, Jinan 250353, Peoples R China
  • [ 5 ] [Zou, Juan]Qufu Normal Univ, Sch Math & Sci, Qufu, Shandong, Peoples R China

通讯作者信息:

  • [Guo, Longkun]Qilu Univ Technol, Sch Comp Sci, Room 420, Jinan 250353, Peoples R China

电子邮件地址:

查看成果更多字段

相关关键词:

相关文章:

来源 :

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE

ISSN: 1532-0626

年份: 2021

期: 17

卷: 35

2 . 0 0 0

JCR@2022

ESI高被引阀值:87

JCR分区:3

被引次数:

WoS核心集被引频次: 0

SCOPUS被引频次:

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

万方被引频次:

中文被引频次:

近30日浏览量: 0

归属院系:

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