Indexed by:
Abstract:
In recent years, submodularity has been found in a wide range of connections and applications with different scientific fields. However, many applications in practice do not fully meet the characteristics of diminishing returns. In this paper, we consider the problem of maximizing unconstrained non-negative weakly-monotone non-submodular set function. The generic submodularity ratio gamma is a bridge connecting the non-negative monotone functions and the submodular functions, and no longer applicable to the non-monotone functions. We study a class of non-monotone functions, define as the weakly-monotone function, redefine the submodular ratio related to it and name it weaklymonotone submodularity ratio (gamma) over cap, propose a deterministic double greedy algorithm, which implements the (gamma) over cap/(gamma) over cap +2 approximation of the maximizing unconstrained non-negative weakly-monotone function problem. When (gamma) over cap. = 1, the algorithm achieves an approximate guarantee of 1/3, achieving the same ratio as the deterministic algorithm for the unconstrained submodular maximization problem.
Keyword:
Reprint Author's Address:
Source :
COMPUTATIONAL DATA AND SOCIAL NETWORKS, CSONET 2021
Year: 2021
Volume: 13116
Page: 50-58
Cited Count:
WoS CC Cited Count: 1
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 11
Affiliated Colleges: