M.Sc Thesis

M.Sc StudentMizrachi Eyal
SubjectSubmodular Maximization with Mixed Packing and Covering
DepartmentDepartment of Computer Science
Supervisor ASSOCIATE PROF. Roy Schwartz


Motivated by applications in machine learning, such as subset selection and data summarization, we consider the problem of maximizing a monotone submodular function subject to mixed packing and covering constraints.

We present a tight approximation algorithm that for any constant ε>0 achieves a guarantee of 1-1/e- ε while violating only the covering constraints by a multiplicative factor of 1- ε.

Our algorithm is based on a novel enumeration method, which unlike previously known enumeration techniques, can handle both packing and covering constraints.

Our algorithm consists of three steps: pre-processing, solving the multi-linear relaxation, and a post-processing step.

The pre-processing step enumerates over all large elements in some optimal solution, such that only small elements are left in the ground-set. However, when considering covering constraints, we cannot enumerate over all the large elements, since unlike packing constraints, there can be O(N) of them in the optimal solution.

The next step would be to formulate and solve the multi-linear relaxation for the residual problem, to get a fractional solution.

We can then round the fractional solution, which combined with the pre-processing step, achieves an approximation to the original problem. Lastly, we employ a post-processing step, in order to avoid a violation of the packing constraints, and achieve a violation of the covering constraints only, without compromising the value of the target function.

We extend the above main result by additionally handling a matroid independence constraints as well as finding (approximate) pareto set optimal solutions when multiple submodular objectives are present.