Instruct: Identify the main and secondary category of Arxiv papers based on the titles and abstracts
Query: Submodular Maximization Beyond Non-negativity: Guarantees, Fast
  Algorithms, and Applications   It is generally believed that submodular functions -- and the more general
class of $\gamma$-weakly submodular functions -- may only be optimized under
the non-negativity assumption $f(S) \geq 0$. In this paper, we show that once
the function is expressed as the difference $f = g - c$, where $g$ is monotone,
non-negative, and $\gamma$-weakly submodular and $c$ is non-negative modular,
then strong approximation guarantees may be obtained. We present an algorithm
for maximizing $g - c$ under a $k$-cardinality constraint which produces a
random feasible set $S$ such that $\mathbb{E} \left[ g(S) - c(S) \right] \geq
(1 - e^{-\gamma} - \epsilon) g(OPT) - c(OPT)$, whose running time is $O
(\frac{n}{\epsilon} \log^2 \frac{1}{\epsilon})$, i.e., independent of $k$. We
extend these results to the unconstrained setting by describing an algorithm
with the same approximation guarantees and faster $O(\frac{n}{\epsilon}
\log\frac{1}{\epsilon})$ runtime. The main techniques underlying our algorithms
are two-fold: the use of a surrogate objective which varies the relative
importance between $g$ and $c$ throughout the algorithm, and a geometric sweep
over possible $\gamma$ values. Our algorithmic guarantees are complemented by a
hardness result showing that no polynomial-time algorithm which accesses $g$
through a value oracle can do better. We empirically demonstrate the success of
our algorithms by applying them to experimental design on the Boston Housing
dataset and directed vertex cover on the Email EU dataset.

28
The categories of this paper are: alg-geom
27
The categories of this paper are: comp-gas
20
The categories of this paper are: acc-phys
32
The categories of this paper are: atom-ph
29
The categories of this paper are: funct-an
16
The categories of this paper are: stat
31
The categories of this paper are: ao-sci
8
The categories of this paper are: hep-ex
15
The categories of this paper are: nucl-ex
26
The categories of this paper are: bayes-an
9
The categories of this paper are: nlin
34
The categories of this paper are: chem-ph
30
The categories of this paper are: q-alg
23
The categories of this paper are: solv-int
0
The categories of this paper are: hep-ph
7
The categories of this paper are: hep-th