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

作者:

Yang, Ruiqi (Yang, Ruiqi.) | Xu, Dachuan (Xu, Dachuan.) (学者:徐大川) | Jiang, Yanjun (Jiang, Yanjun.) | Wang, Yishui (Wang, Yishui.) | Zhang, Dongmei (Zhang, Dongmei.)

收录:

EI Scopus SCIE

摘要:

We study a robust parameterized submodular function maximization inspired by [Mitrovic, S, I Bogunovic, A Norouzi-Fardand Jakub Tarnawski (2017). Streaming robust submodular maximization: A partitioned thresholding approach. In Proc. NIPS, pp. 4560-4569] and [Bogunovic, I, J Zhao and V Cevher (2018). Robust maximization of nonsubmodular objectives. In Proc. AISTATS, pp. 890-899]. In our setting, given a parameterized set function, there are two additional twists. One is that elements arrive in a streaming style, and the other is that there are at most tau items deleted from the algorithm's memory when the stream is finished. The goal is to choose a robust set from the stream such that the robust ratio is maximized. We propose a two-phase algorithm for maximizing a normalized monotone robust parameterized submodular function with a cardinality constraint and show the robust ratio is close to a constant as k -> infinity. In the end, we empirically demonstrate the performance of our algorithm on deletion robust support selection problem.

关键词:

approximation algorithm robust stream Submodular function

作者机构:

  • [ 1 ] [Yang, Ruiqi]Beijing Univ Technol, Dept Operat Res & Sci Comp, 100 Pingleyuan, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, 100 Pingleyuan, Beijing 100124, Peoples R China
  • [ 3 ] [Jiang, Yanjun]Ludong Univ, Sch Math & Stat Sci, 186 Hongqi Middle Rd, Yantai 264025, Shandong, Peoples R China
  • [ 4 ] [Wang, Yishui]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China
  • [ 5 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China

通讯作者信息:

  • [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China

查看成果更多字段

相关关键词:

相关文章:

来源 :

ASIA-PACIFIC JOURNAL OF OPERATIONAL RESEARCH

ISSN: 0217-5959

年份: 2019

期: 4

卷: 36

1 . 4 0 0

JCR@2022

ESI学科: ENGINEERING;

ESI高被引阀值:52

被引次数:

WoS核心集被引频次: 10

SCOPUS被引频次: 9

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

万方被引频次:

中文被引频次:

近30日浏览量: 2

归属院系:

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