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

Author:

Cui, Min (Cui, Min.) | Du, Donglei (Du, Donglei.) | Xu, Dachuan (Xu, Dachuan.) | Yang, Ruiqi (Yang, Ruiqi.)

Indexed by:

EI Scopus SCIE

Abstract:

Many combinatorial optimization problems can be reduced to submodular optimization problems. However, many cases in practical applications do not fully comply with the diminishing returns characteristic. This paper studies the problem of maximizing weakly-monotone non-submodular non-negative set functions without constraints, and extends the normal submodular ratio to weakly-monotone submodular ratio (gamma) over cap. In this paper, two algorithms are given for the above problems. The first one is a deterministic greedy approximation algorithm, which realizes the approximation ratio of <<(gamma)over cap>/<<(gamma)over cap>+2 When (gamma) over cap = 1, the approximate ratio is 1/3, which matches the ratio of the best deterministic algorithm known for the maximization of submodular function without constraints. The second algorithm is a random greedy algorithm, which improves the approximation ratio to (gamma) over cap/(gamma) over cap +1. When (gamma) over cap = 1, the approximation ratio is 1/2, the same as the best algorithm for the maximization of unconstrained submodular set functions.

Keyword:

Greedy Unconstrained Weakly-monotone Non-submodular

Author Community:

  • [ 1 ] [Cui, Min]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 3 ] [Yang, Ruiqi]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 4 ] [Du, Donglei]Univ New Brunswick, Fac Management, Fredericton, NB E3B 5A3, Canada
  • [ 5 ] [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 :

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN: 1382-6905

Year: 2023

Issue: 1

Volume: 45

1 . 0 0 0

JCR@2022

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:1422/10902190
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.