Indexed by:
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:
Reprint Author's Address:
Email:
Source :
COMPUTING AND COMBINATORICS, COCOON 2019
ISSN: 0302-9743
Year: 2019
Volume: 11653
Page: 651-662
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: