Maximize Monotone BP Functions in Submodular Optimization

【作者】 陈玲；

【导师】 张晓岩；

【作者基本信息】 南京师范大学 ， 运筹学与控制论， 2020， 硕士

【摘要】 BP问题是指在某些约束情况下最大化次模+超模函数,其中两个函数都是非负和单调的。这类问题来源于机器学习,数据科学和人工智能等交叉领域,具有重要的应用价值。本文中我们考虑BP问题的四种变形。首先是在均匀拟阵约束下的在线BP最大化问题,该问题中物品是以在线的方式一个一个到达的,为此我们提出了一种具有常因子竞争比的在线算法。第二个是二分拟阵约束下的在线BP最大化问题,为此我们给出了一种具有常因子竞争比的随机在线算法。第三个问题是在(1,l)划分拟阵约束下的在线BP最大化问题,它是第二个问题的一个推广,为此我们提出了两种具有常因子竞争比的在线算法,一种是随机算法,另一种是确定性算法。最后一个问题是服从均匀拟阵和一般拟阵约束的离线两阶段BP最大化问题,为此我们给出了一种具有常因子近似比的近似算法。更多还原

【Abstract】 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 type of problems arises naturally in many applications in machine learning,data science and artificial intelligence.We consider four variants of the BP problem.The first problem is an online BP maximization problem subject to a uniform matroid constraint when the items arrive one-by-one in an online fashion,for which we offer an online algorithm with constant competitive ratio.The second problem is an online BP maximization problem subject to a binary partition matroid constraint,for which we present a randomized online algorithm with constant competitive ratio.The third problem is an online BP maximization problem subject to a(1,l)partition matroid constraint which is the generalization of the second problem.For this problem,we present two online algorithms with constant competitive ratios in which one is a random algorithm and the other one is a deterministic algorithm.The last problem is an offline two-stage BP maximization problem subject to a uniform matroid and general matroid constraints,for which we propose an approximation algorithm with constant approximation ratio.更多还原