Randomized Parallel Algorithm for Maximizing Nonsubmodular Function Subject to Cardinality Constraint

The problem of maximization submodular functions with a cardinality constraint has been extensively researched in recent years. Balkanski and Singer were the first to study this class problem. Subsequently, Chekuri and Kent recently extended these results to more general constraints, that is, k-cardinality constraint, partition and laminar matroids, matching, knapsack constraints, and including their intersection. They proposed a (1 − 1/e − 𝜀) approximation randomized-parallel-greedy algorithm which are poly-logarithmic adaptivity. However, these existing approaches are hardly extended to the nonsubmodular case. In this paper, we investigate the problem of maximization on a nonsubmodular function subject to a cardinality constraint, provided the objective function is specified by a generic submodularity ratio γ. We design a (1 − e−γ − 𝜀)-approximation Greedy algorithm by using the technical aspects to maximize the multilinear relaxation of the object function under the k-cardinality constraints. The adaptive of multilinear relaxation is O(log n/𝜀2); the number of oracle is Õ(n/𝜀4).