AN ADAPTIVE ALGORITHM FOR MAXIMIZATION OF NON-SUBMODULAR FUNCTION WITH A MATROID CONSTRAINT.

In the paper, we design an adaptive algorithm for non-submodular set function maximization over a single matroid constraint. We measure the deviation of the set function from fully submodular with the help of the generic submodularity ratio γ. The adaptivity quantifies the information theoretic complexity of oracle optimization for parallel computations. We propose a new approximation algorithm based on the continuous greedy approach and prove that the algorithm could obtain a fractional solution with approximation ratio (1 -- ... -- O(ϵ)) in O(log n log(k/γϵ)/ϵ^-2 log n log(1/γ)--ϵ^-1log(1--ϵ) adaptive rounds. We then use the contention resolution schemes to convert the fractional solution to a discrete one with γ(1 -- e^-1)(1 -- ... -- O(ϵ))-approximation. [ABSTRACT FROM AUTHOR]