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 gamma. 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 - e(-gamma 2) - O(epsilon)) in O(log n log(k/gamma epsilon)/epsilon(-2) log n log(1/gamma) - epsilon(-1) log(1-epsilon)) then use the contention resolution schemes to convert the fractional solution to a discrete one with gamma (1 - e(-1))(1 - e(-gamma 2) - O(epsilon))-approximation.

Automated summary

In this paper, we propose an adaptive algorithm for maximizing non-submodular set functions under a single matroid constraint. The algorithm is based on the continuous greedy approach and measures the deviation of the set function from submodularity using the generic submodularity ratio gamma. We prove the approximation ratio of the algorithm and provide a solution for converting the fractional solution to a discrete one.