Name
Abstract | ||
|---|---|---|
“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 \cite{indyk2018composable}, where they designed composable core-sets with the optimal approximation bound of $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 $C^{k^2}$ 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. |
Year | Venue | Field |
|---|---|---|
2019 | international conference on machine learning | Data modeling,Data set,Point process,Algorithm,Greedy algorithm,Tilde,Local search (optimization),Optimization problem,Mathematics,Maximization |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sepideh Mahabadi | 1 | 77 | 7.94 |
| Piotr Indyk | 2 | 10925 | 918.34 |
| Shayan Oveis Gharan | 3 | 323 | 26.63 |
| A. Rezaei | 4 | 0 | 2.03 |