  Given a set of $n$ vectors in $\mathbb{R}^d$, the goal of the
\emph{determinant maximization} problem is to pick $k$ vectors with the maximum
volume. Determinant maximization is the MAP-inference task for determinantal
point processes (DPP) and has recently received considerable attention for
modeling diversity. As most applications for the problem use large amounts of
data, this problem has been studied in the relevant \textit{composable coreset}
setting. In particular, [Indyk-Mahabadi-OveisGharan-Rezaei--SODA'20, ICML'19]
showed that one can get composable coresets with optimal approximation factor
of $\tilde O(k)^k$ for the problem, and that a local search algorithm achieves
an almost optimal approximation guarantee of $O(k)^{2k}$. In this work, we show
that the widely-used Greedy algorithm also provides composable coresets with an
almost optimal approximation factor of $O(k)^{3k}$, which improves over the
previously known guarantee of $C^{k^2}$, and supports the prior experimental
results showing the practicality of the greedy algorithm as a coreset. Our main
result follows by showing a local optimality property for Greedy: swapping a
single point from the greedy solution with a vector that was not picked by the
greedy algorithm can increase the volume by a factor of at most $(1+\sqrt{k})$.
This is tight up to the additive constant $1$. Finally, our experiments show
that the local optimality of the greedy algorithm is even lower than the
theoretical bound on real data sets.

Data Structures and Algorithms;Machine Learning