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

Author:

Cui, Min (Cui, Min.) | Du, Donglei (Du, Donglei.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Yang, Ruiqi (Yang, Ruiqi.)

Indexed by:

CPCI-S EI Scopus

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:

Submodularity ratio Unconstrained Non-submodular optimization

Author Community:

  • [ 1 ] [Cui, Min]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 2 ] [Du, Donglei]Univ New Brunswick, Fac Management, Fredericton, NB E3B 5A3, Canada
  • [ 3 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 4 ] [Yang, Ruiqi]Univ Chinese Acad Sci, Sch Math Sci, Beijing 100049, Peoples R China

Reprint Author's Address:

Show more details

Related Keywords:

Related Article:

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:

Online/Total:789/10657751
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.