Name
Abstract | ||
|---|---|---|
Given a set S of points in a metric space, and a diversity measure div( ) dened over subsets of S, the goal of the diversity maximization problem is to nd a subset T S of size k that maximizes div(T ). Motivated by applications in massive data processing, we consider the composable coreset framework in which a coreset for a diversity measure is called -composable, if for any collection of sets and their corresponding coresets, the maximum diversity of the union of the coresets approximates the maximum diversity of the union of the sets. We present composable coresets with near-optimal approximation factors for several notions of diversity, including remote-clique, remote-cycle, and remote-tree. We also prove a general lower bound on the approximation factor of composable coresets for a large class of diversity maximization problems. |
Year | Venue | Field |
|---|---|---|
2015 | CCCG | Discrete mathematics,Combinatorics,Data processing,Diversity measure,Upper and lower bounds,Metric space,Mathematics,Maximization,Coreset |
DocType | Citations | PageRank |
Conference | 5 | 0.41 |
References | Authors | |
11 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sepideh Aghamolaei | 1 | 5 | 0.41 |
| Majid Farhadi | 2 | 5 | 0.41 |
| Hamid Zarrabi-Zadeh | 3 | 111 | 13.63 |