Composable Coresets for Determinant Maximization: Greedy is Almost Optimal

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. 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.