Submodular Maximization Problems In Combinatorial Optimization

Submodular maximization problem has been widely studied in machine learning and economics.In this thesis,we consider four problems related to submodular maximization problem.The first is an online version of the Social Welfare Problem(SWP)which has important applications in combinatorial auctions and has been studied extensively in computational economics.In SWP,we try to allocate a set V of n items to m agents by partitioning the items set V into m subsets S₁,S₂,···,S_m in order to maximize the total social welfare (?)V_i(S_i) of all agents,where each V_i is a non-negative monotone submodular function.This problem can be formulated as the submodular maximization problem subject to a partition matroid.We consider a generalized online version of this problem in which the sets defining an arbitrary partition matroid arrive online in a random order,and we use a randomized algorithm to maximize the objective function(submodular function)subject to this matroid.The second problem is submodular diversity problem.The goal is to maximize the sum of a monotone submodular function combining with a sum-sum diversity function which satisfies the relaxed triangle inequality under the cardinality constraint.The next two problems are related to two-stage submodular maximization problem.The one is that objective function composes of non-negative monotone submodular functions while the first-stage has a knapsack constraint and the second-stage has k matroid constraints.We present a 1/2(1-e^-1/(k+1)) approximation algorithm for this problem.The other one is that objective function consists of the differences of non-negative monotone submodular functions and non-negative monotone modular functions while the first-stage has a cardinality constraint and the second-stage has k matroid constraints.We present two bifactor algorithms for this problem,one deterministic and one randomized with improved time complexity.