Guarantees for Greedy Maximization of Non-submodular Functions with Applications. (arXiv:1703.02100v1 [cs.DM])

We investigate the performance of the Greedy algorithm for cardinality constrained maximization of non-submodular nondecreasing set functions. While there are strong theoretical guarantees on the performance of Greedy for maximizing submodular functions, there are few guarantees for non-submodular ones. However, Greedy enjoys strong empirical performance for many important non-submodular functions, e.g., the Bayesian A-optimality objective in experimental design. We prove theoretical guarantees supporting the empirical performance. Our guarantees are characterized by the (generalized) submodularity ratio $\gamma$ and the (generalized) curvature $\alpha$. In particular, we prove that Greedy enjoys a tight approximation guarantee of $\frac{1}{\alpha}(1- e^{-\gamma\alpha})$ for cardinality constrained maximization. In addition, we bound the submodularity ratio and curvature for several important real-world objectives, e.g., the Bayesian A-optimality objective, the determinantal function of a square submatrix and certain linear programs with combinatorial constraints. We experimentally validate our theoretical findings for several real-world applications.

from cs.AI updates on arXiv.org http://ift.tt/2mz2Zm4
via IFTTT