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

Author:

Liu, Zhicheng (Liu, Zhicheng.) | Jin, Jing (Jin, Jing.) | Chang, Hong (Chang, Hong.) | Du, Donglei (Du, Donglei.) | Zhang, Xiaoyan (Zhang, Xiaoyan.)

Indexed by:

EI Scopus SCIE

Abstract:

The concept of submodularity finds wide applications in data science, artificial intelligence, and machine learning, providing a boost to the investigation of new ideas, innovative techniques, and creative algorithms to solve different submodular optimization problems arising from a diversity of applications. However pure submodular or supermodular problems only represent a small portion of the problems we are facing in real life applications. The main focus of this work is to consider a non-submodular function maximization problem subject to a cardinality constraint, where the objective function is the sum of a monotone gamma-weakly submodular function and a supermodular function. This problem includes some previously studied problems as special cases, such as the submodular+supermodular maximization problem when gamma =1, and the gamma-weakly submodular function maximization problem when the supermodular function is void. We present greedy algorithms for this generalized problem under both offline and streaming models, improving existing results.(c) 2022 Elsevier B.V. All rights reserved.

Keyword:

Greedy algorithm Non-submodular function maximization Cardinality constraint Streaming model Offline model

Author Community:

  • [ 1 ] [Liu, Zhicheng]Beijing Univ Technol, Beijing Inst Sci & Engn Comp, Beijing 100124, Peoples R China
  • [ 2 ] [Jin, Jing]Nanjing Normal Univ, Coll Taizhou, Tiazhou 225300, Peoples R China
  • [ 3 ] [Chang, Hong]Nanjing Normal Univ, Inst Math, Sch Math Sci, Nanjing 210023, Peoples R China
  • [ 4 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Sch Math Sci, Nanjing 210023, Peoples R China
  • [ 5 ] [Du, Donglei]Univ New Brunswick, Fac Management, Fredericton, NB E3B5A3, Canada

Reprint Author's Address:

Show more details

Related Keywords:

Source :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

Year: 2022

Volume: 931

Page: 49-55

1 . 1

JCR@2022

1 . 1 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:46

JCR Journal Grade:4

CAS Journal Grade:4

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:1271/10904277
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.