• 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 and 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-approximation in 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, runs in adaptive rounds and requires queries, where is the Continuous generic submodularity ratio. © 2020, Springer Nature Switzerland AG.

Keyword:

Combinatorial mathematics Approximation algorithms

Author Community:

  • [ 1 ] [Zhang, Hongxiang]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 2 ] [Xu, Dachuan]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 3 ] [Guo, Longkun]Shandong Key Laboratory of Computer Networks, School of Computer Science and Technology, Shandong Computer Science Center, Qilu University of Technology (Shandong Academy of Sciences), Jinan; 250353, China
  • [ 4 ] [Tan, Jingjing]School of Mathematics and Information Science, Weifang University, Weifang; 261061, China

Reprint Author's Address:

  • [guo, longkun]shandong key laboratory of computer networks, school of computer science and technology, shandong computer science center, qilu university of technology (shandong academy of sciences), jinan; 250353, china

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2020

Volume: 12273 LNCS

Page: 520-531

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 7

Affiliated Colleges:

Online/Total:730/10642059
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.