• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

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

Indexed by:

CPCI-S EI Scopus

Abstract:

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.

Keyword:

Multilinear relaxation Parallel algorithm Nonsubmodular Cardinality constraints

Author Community:

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

Reprint Author's Address:

Show more details

Related Keywords:

Source :

COMPUTING AND COMBINATORICS (COCOON 2020)

ISSN: 0302-9743

Year: 2020

Volume: 12273

Page: 520-531

Cited Count:

WoS CC Cited Count: 1

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:1091/5329332
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.