# Composable Core-sets for Determinant Maximization: A Simple Near-Optimal Algorithm

arXiv: https://arxiv.org/abs/1907.03197 · HTML: https://mlsanity.com/paper/1907.03197/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2019.

## Built on by (most cited first, 9 of 9)

- [Contextual Bandits with Large Action Spaces: Made Practical](https://mlsanity.com/paper/2207.05836/) (2022)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Lazy and Fast Greedy MAP Inference for Determinantal Point Process](https://mlsanity.com/paper/2206.05947/) (2022)
- [Tight Bounds for Volumetric Spanners and Applications](https://mlsanity.com/paper/2310.00175/) (2023)
- [Core-sets for Fair and Diverse Data Summarization](https://mlsanity.com/paper/2310.08122/) (2023)
- [Sequential Recommendation with Controllable Diversification: Representation Degeneration and Diversity](https://mlsanity.com/paper/2306.11986/) (2023)
- [Towards Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [Composable Core-sets for Diversity Approximation on Multi-Dataset Streams](https://mlsanity.com/paper/2308.05878/) (2023)
- [Composable Coresets for Determinant Maximization: Greedy is Almost Optimal](https://mlsanity.com/paper/2309.15286/) (2023)

## Abstract (arXiv)

``Composable core-sets'' are an efficient framework for solving optimization problems in massive data models. In this work, we consider efficient construction of composable core-sets for the determinant maximization problem. This can also be cast as the MAP inference task for determinantal point processes, that have recently gained a lot of interest for modeling diversity and fairness. The problem was recently studied in [IMOR'18], where they designed composable core-sets with the optimal approximation bound of tilde O(k)k. On the other hand, the more practical Greedy algorithm has been previously used in similar contexts. In this work, first we provide a theoretical approximation guarantee of O(Ck2) for the Greedy algorithm in the context of composable core-sets; Further, we propose to use a Local Search based algorithm that while being still practical, achieves a nearly optimal approximation bound of O(k)2k; Finally, we implement all three algorithms and show the effectiveness of our proposed algorithm on standard data sets.