• 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.) (Scholars:徐大川) | Zhang, Dongmei (Zhang, Dongmei.)

Indexed by:

EI

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 β and curvature α. In particular, we prove that the greedy algorithm enjoys a tight approximation guarantee of (Formula Presented) 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. © Springer Nature Switzerland AG 2019.

Keyword:

Combinatorial mathematics Approximation algorithms Optimization Combinatorial optimization

Author Community:

  • [ 1 ] [Zhang, Zhenning]College of Applied Sciences, Beijing University of Technology, Beijing; 100124, China
  • [ 2 ] [Liu, Bin]School of Mathematical Science, Ocean University of China, Qingdao; 266100, China
  • [ 3 ] [Wang, Yishui]Shenzhen Institutes of Advanced Technology, Chinese Academy of Sciences, Shenzhen; 518055, China
  • [ 4 ] [Xu, Dachuan]Department of Operations Research and Scientific Computing, Beijing University of Technology, Beijing; 100124, China
  • [ 5 ] [Zhang, Dongmei]School of Computer Science and Technology, Shandong Jianzhu University, Jinan; 250101, China

Reprint Author's Address:

  • [wang, yishui]shenzhen institutes of advanced technology, chinese academy of sciences, shenzhen; 518055, china

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2019

Volume: 11653 LNCS

Page: 651-662

Language: English

Cited Count:

WoS CC Cited Count:

SCOPUS Cited Count: 5

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 0

Affiliated Colleges:

Online/Total:1094/5328396
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.