收录:
摘要:
The BP problem maximizes the sum of a suBmodular function and a suPermodular function(BP) subject to some constraints, where both functions are nonnegative and monotonic. This problem has been widely studied under the single-stage setting. In this paper, we consider a variant of the BP maximization problem. The problem is a two-stage BP maximization problem subject to a p-matroid constraint, for which we propose an approximation algorithm with constant approximation ratio parameterized by the curvatures of the two functions involved.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
THEORETICAL COMPUTER SCIENCE
ISSN: 0304-3975
年份: 2024
卷: 994
1 . 1 0 0
JCR@2022
归属院系: