Regularized Submodular Maximization With a <italic>k</italic>-Matroid Intersection Constraint

Abstract

With the development of the Internet and the emergence of various social-media platforms, designing approximation algorithms for optimization problems such as the influence maximization in social networks has received widespread attention. With considering cost, these problems are typically modeled as the regularized submodular optimization, in which a regularized submodular function is expressed as the difference of a nonnegative submodular revenue function $f(\cdot )$ and a nonnegative modular cost function $c(\cdot )$ . In this paper, we consider two kinds of regularized submodular maximization problems with a $k$ -matroid intersection constraint. When $f(\cdot )$ is additionally monotone, we provide a distorted greedy algorithm with a tight constant bicriteria approximation ratio and a time complexity of $O(n^{2})$ . When $f(\cdot )$ is nonmonotone, we combine the distorted greedy algorithm with a simple stochastic process to design a constant bicriteria approximation algorithm with a time complexity of $O(kn^{2})$ . To our knowledge, this is the first paper to design polynomial-time algorithms for the regularized submodular maximization with a $k$ -matroid intersection constraint.

Keywords

• Algorithm design and analysis
• distorted greedy
• k-matroid intersection
• monotonicity
• regularized submodularity