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

Author:

Zhang, Zhenning (Zhang, Zhenning.) | Liu, Bin (Liu, Bin.) | Wang, Yishui (Wang, Yishui.) | Xu, Dachuan (Xu, Dachuan.) | Zhang, Dongmei (Zhang, Dongmei.)

Indexed by:

CPCI-S EI Scopus

Abstract:

Although submodular maximization generalizes many fundamental problems in discrete optimization, lots of real-world problems are non-submodular. In this paper, we consider the maximization problem of non-submodular function with a knapsack constraint, and explore the performance of the greedy algorithm. Our guarantee is characterized by the submodularity ratio beta and curvature alpha. In particular, we prove that the greedy algorithm enjoys a tight approximation guarantee of 1/alpha (1 - e(-alpha beta)) for the above problem. To our knowledge, it is the first tight constant factor for this problem. In addition, we experimentally validate our algorithm by an important application, the Bayesian A-optimality.

Keyword:

Submodularity ratio Knapsack constraint Curvature Non-submodular Diminishing-return ratio

Author Community:

  • [ 1 ] [Zhang, Zhenning]Beijing Univ Technol, Coll Appl Sci, Beijing 100124, Peoples R China
  • [ 2 ] [Liu, Bin]Ocean Univ China, Sch Math Sci, Qingdao 266100, Peoples R China
  • [ 3 ] [Wang, Yishui]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China
  • [ 4 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Sci Comp, Beijing 100124, Peoples R China
  • [ 5 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Source :

COMPUTING AND COMBINATORICS, COCOON 2019

ISSN: 0302-9743

Year: 2019

Volume: 11653

Page: 651-662

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:1441/10902043
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.