Title: A New Approximation Guarantee for Monotone Submodular Function Maximization via Discrete Convexity,
Abstract: In monotone submodular function maximization, approximation guarantees based
on the curvature of the objective function have been extensively studied in the
literature. However, the notion of curvature is often pessimistic, and we
rarely obtain improved approximation guarantees, even for very simple objective
functions.
In this paper, we provide a novel approximation guarantee by extracting an
M$^\natural$-concave function $h:2^E \to \mathbb R_+$, a notion in discrete
convex analysis, from the objective function $f:2^E \to \mathbb R_+$. We
introduce the notion of $h$-curvature, which measures how much $f$ deviates
from $h$, and show that we can obtain a $(1-\gamma/e-\epsilon)$-approximation
to the problem of maximizing $f$ under a cardinality constraint in polynomial
time for any constant $\epsilon > 0$. Then, we show that we can obtain
nontrivial approximation guarantees for various problems by applying the
proposed algorithm.