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

Author:

Ji, Sai (Ji, Sai.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Li, Min (Li, Min.) | Wang, Yishui (Wang, Yishui.) | Zhang, Dongmei (Zhang, Dongmei.)

Indexed by:

EI Scopus SCIE

Abstract:

The problem of maximizing the sum of a constrained submodular and a supermodular function has many applications such as social networks, machine learning, and artificial intelligence. In this article, we study the monotone submodular + supermodular maximization problem under a cardinality constraint and a p-system constraint, respectively. For each problem, we provide a stochastic algorithm and prove the approximation ratio of each algorithm theoretically. Since the algorithm of the latter problem can also solve the former problem, we do some numerical experiments of the two algorithms to compare the time as well as the quality of the two algorithms in solving the former problem.

Keyword:

submodular plus supermodular maximization approximation algorithm stochastic greedy constrained

Author Community:

  • [ 1 ] [Ji, Sai]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing, Peoples R China
  • [ 3 ] [Ji, Sai]Chinese Acad Sci, Acad Math & Syst Sci, Beijing, Peoples R China
  • [ 4 ] [Li, Min]Shandong Normal Univ, Sch Math & Stat, Jinan, Peoples R China
  • [ 5 ] [Wang, Yishui]Univ Sci & Technol Beijing, Sch Math & Phys, Beijing, Peoples R China
  • [ 6 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

Reprint Author's Address:

  • [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

Show more details

Related Keywords:

Related Article:

Source :

CONCURRENCY AND COMPUTATION-PRACTICE & EXPERIENCE

ISSN: 1532-0626

Year: 2021

Issue: 17

Volume: 35

2 . 0 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:87

JCR Journal Grade:3

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count: 1

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 2

Affiliated Colleges:

Online/Total:366/10642636
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.