收录:
摘要:
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.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
THEORETICAL COMPUTER SCIENCE
ISSN: 0304-3975
年份: 2022
卷: 931
页码: 49-55
1 . 1
JCR@2022
1 . 1 0 0
JCR@2022
ESI学科: COMPUTER SCIENCE;
ESI高被引阀值:46
JCR分区:4
中科院分区:4
归属院系: