Maximize Monotone BP Functions In Submodular Optimization

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.