SODA

\documentclass[11pt]{article}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amsmath,amssymb,amsthm,mathtools}
\usepackage[margin=1in]{geometry}
\usepackage[hidelinks]{hyperref}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}

\title{Submodular Maximization via Fast Gradient Oracles:\\
       A Nearly Linear-Time Framework}
\author{First Last\thanks{University of Example, \texttt{[email protected]}.} \and
        Jane Doe\thanks{Example Research Labs, \texttt{[email protected]}.}}
\date{\today}

\begin{document}
\maketitle

\begin{abstract}
We give a nearly linear-time framework for submodular function
maximization subject to matroid constraints, improving the prior best
running time of $O(n^2)$ to $O(n \log^3 n)$. Our framework uses a new
fast gradient oracle and a hierarchical decomposition of the ground set.
\end{abstract}

\section{Introduction}
The classical greedy algorithm runs in $O(n^2)$ time; reducing to nearly
linear time has been an open problem.

\section{Preliminaries}
\begin{definition}
$f: 2^V \to \mathbb{R}$ is submodular if $f(A \cup \{v\}) - f(A) \ge
f(B \cup \{v\}) - f(B)$ for all $A \subseteq B$, $v \notin B$.
\end{definition}

\section{Our Framework}
\begin{lemma}\label{lem:oracle}
Given preprocessing time $O(n \log^2 n)$, one can answer marginal queries
in $O(\log n)$ amortized time.
\end{lemma}

\begin{theorem}\label{thm:main}
For submodular maximization under matroid constraints there is an
$(1-1/e-\varepsilon)$-approximation algorithm running in
$O(n \log^3 n \cdot \mathrm{poly}(\varepsilon^{-1}))$ time.
\end{theorem}

\begin{proof}[Proof sketch]
We partition the ground set hierarchically and compute approximate
marginal gains at each level. The guarantee follows from the continuous
greedy analysis adapted to our discretization.
\end{proof}

\section{Lower Bound Discussion}
A running time of $\Omega(n \log n)$ is necessary; whether
$\mathrm{poly}(\log n)$ factors can be avoided is open.

\section{Conclusion}
Nearly linear time submodular optimization is tractable via fast oracle
design.

\begin{thebibliography}{9}
\bibitem{nemhauser} G.~Nemhauser, L.~Wolsey, M.~Fisher. \emph{An analysis
of approximations for maximizing submodular set functions-I.}
Math.\ Prog., 1978.
\bibitem{calinescu} G.~C\u alinescu, C.~Chekuri, M.~P\'al, J.~Vondr\'ak.
\emph{Maximizing a monotone submodular function subject to a matroid
constraint.} SICOMP, 2011.
\end{thebibliography}

\end{document}