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

作者:

Yang, Ruiqi (Yang, Ruiqi.) | Gu, Shuyang (Gu, Shuyang.) | Gao, Chuangen (Gao, Chuangen.) | Wu, Weili (Wu, Weili.) | Wang, Hua (Wang, Hua.) | Xu, Dachuan (Xu, Dachuan.) (学者:徐大川)

收录:

CPCI-S EI Scopus

摘要:

We consider a two-stage submodular maximization under pmatroid (or p-extendible) constraints. In the model, we are given a collection of submodular functions and some p-matroid (or extendible) system constraints for each of these functions, one need to choose a representative set with a cardinality constraint and simultaneously select a series of subsets that are restricted to the representative set for all functions, the aim is to maximize the average of the summarization of these function values. We extend the two-stage submodular maximization under single matroid to handle p-matroid (or p-extendible) constraints, and derive constant approximation ratio algorithms for the two problems, respectively. In the end, we empirically demonstrate the efficiency of our method on some datasets.

关键词:

Submodular maximization Approximation algorithms Independence system constraints

作者机构:

  • [ 1 ] [Yang, Ruiqi]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Gu, Shuyang]Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75080 USA
  • [ 4 ] [Wu, Weili]Univ Texas Dallas, Dept Comp Sci, Richardson, TX 75080 USA
  • [ 5 ] [Gao, Chuangen]Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China
  • [ 6 ] [Wang, Hua]Shandong Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

通讯作者信息:

  • 徐大川

    [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China

查看成果更多字段

相关关键词:

相关文章:

来源 :

ALGORITHMIC ASPECTS IN INFORMATION AND MANAGEMENT, AAIM 2019

ISSN: 0302-9743

年份: 2019

卷: 11640

页码: 329-340

语种: 英文

被引次数:

WoS核心集被引频次: 1

SCOPUS被引频次: 1

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

万方被引频次:

中文被引频次:

近30日浏览量: 0

归属院系:

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