Diversity Maximization via Composable Coresets
Sepideh Aghamolaei, Majid Farhadi, Hamid Zarrabi-Zadeh · 2015
Given a set S of points in a metric space, and a diver-sity measure div(·) defined over subsets of S, the goal of the diversity maximization problem is to find a sub-set 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 approxi-mation factor of composable coresets for a large class of diversity maximization problems. 1