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

作者:

Zhang, Hongxiang (Zhang, Hongxiang.) | Xu, Dachuan (Xu, Dachuan.) (学者:徐大川) | Guo, Longkun (Guo, Longkun.) | Tan, Jingjing (Tan, Jingjing.)

收录:

CPCI-S EI Scopus

摘要:

In the paper, we study the adaptivity of maximizing a monotone nonsubmodular function subject to a cardinality constraint. Adaptive approximation algorithm has been previously developed for the similar constrained maximization problem against submodular function, attaining an approximation ratio of (1 - 1/e - epsilon) and O (log n/epsilon(2)) rounds of adaptivity. For more general constraints, Chandra and Kent described parallel algorithms for approximately maximizing the multilinear relaxation of a monotone submodular function subject to either cardinality or packing constraints, achieving a near-optimal (1 - 1/e - epsilon)approximation in O (log(2) m log n/epsilon(4)) rounds. We propose an Expand-Parallel-Greedy algorithm for the multilinear relaxation of a monotone and normalized set function subject to a cardinality constraint based on rounding the multilinear relaxation of the function. The algorithm achieves a ratio of (1 - e(-gamma 2) - epsilon) , runs in O (log n/epsilon(2)) adaptive rounds and requires O ((n log n/epsilon(2))) queries, where gamma is the Continuous generic submodularity ratio.

关键词:

Multilinear relaxation Parallel algorithm Nonsubmodular Cardinality constraints

作者机构:

  • [ 1 ] [Zhang, Hongxiang]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 3 ] [Guo, Longkun]Qilu Univ Technol, Shandong Comp Sci Ctr, Sch Comp Sci & Technol, Shandong Key Lab Comp Networks,Shandong Acad Sci, Jinan 250353, Peoples R China
  • [ 4 ] [Tan, Jingjing]Weifang Univ, Sch Math & Informat Sci, Weifang 261061, Peoples R China

通讯作者信息:

查看成果更多字段

相关关键词:

来源 :

COMPUTING AND COMBINATORICS (COCOON 2020)

ISSN: 0302-9743

年份: 2020

卷: 12273

页码: 520-531

被引次数:

WoS核心集被引频次: 1

SCOPUS被引频次:

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

万方被引频次:

中文被引频次:

近30日浏览量: 0

归属院系:

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