Non-submodular Function Maximization subject to a Matroid Constraint, with Applications

  • 2019-10-08 15:57:22
  • Khashayar Gatmiry, Manuel Gomez-Rodriguez
  • 0

Abstract

The standard greedy algorithm has been recently shown to enjoy approximationguarantees for constrained non-submodular nondecreasing set functionmaximization. While these recent results allow to better characterize theempirical success of the greedy algorithm, they are only applicable to simplecardinality constraints. In this paper, we study the problem of maximizing anon-submodular nondecreasing set function subject to a general matroidconstraint. We first show that the standard greedy algorithm offers anapproximation factor of $\frac{0.4 {\gamma}^{2}}{\sqrt{\gamma r} + 1}$, where$\gamma$ is the submodularity ratio of the function and $r$ is the rank of thematroid. Then, we show that the same greedy algorithm offers a constantapproximation factor of $(1 + 1/(1-\alpha))^{-1}$, where $\alpha$ is thegeneralized curvature of the function. In addition, we demonstrate that theseapproximation guarantees are applicable to several real-world applications inwhich the submodularity ratio and the generalized curvature can be bounded.Finally, we show that our greedy algorithm does achieve a competitiveperformance in practice using a variety of experiments on synthetic andreal-world data.

 

Quick Read (beta)

This feature is not avaialbe for this paper.