Title: Submodular Maximization through the Lens of Linear Programming,
Abstract: The simplex algorithm for linear programming is based on the fact that any
local optimum with respect to the polyhedral neighborhood is also a global
optimum. We show that a similar result carries over to submodular maximization.
In particular, every local optimum of a constrained monotone submodular
maximization problem yields a $1/2$-approximation, and we also present an
appropriate extension to the non-monotone setting. However, reaching a local
optimum quickly is a non-trivial task. Moreover, we describe a fast and very
general local search procedure that applies to a wide range of constraint
families, and unifies as well as extends previous methods. In our framework, we
match known approximation guarantees while disentangling and simplifying
previous approaches. Moreover, despite its generality, we are able to show that
our local search procedure is slightly faster than previous specialized
methods. Furthermore, we resolve an open question on the relation between
linear optimization and submodular maximization; namely, whether a linear
optimization oracle may be enough to obtain strong approximation algorithms for
submodular maximization. We show that this is not the case by providing an
example of a constraint family on a ground set of size $n$ for which, if only
given a linear optimization oracle, any algorithm for submodular maximization
with a polynomial number of calls to the linear optimization oracle will have
an approximation ratio of only $O ( \frac{1}{\sqrt{n}} \cdot \frac{\log
n}{\log\log n} )$.