License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.33
URN: urn:nbn:de:0030-drops-99818
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9981/
Cevallos, Alfonso ;
Eisenbrand, Friedrich ;
Morell, Sarah
Diversity Maximization in Doubling Metrics
Abstract
Diversity maximization is an important geometric optimization problem with many applications in recommender systems, machine learning or search engines among others. A typical diversification problem is as follows: Given a finite metric space (X,d) and a parameter k in N, find a subset of k elements of X that has maximum diversity. There are many functions that measure diversity. One of the most popular measures, called remote-clique, is the sum of the pairwise distances of the chosen elements. In this paper, we present novel results on three widely used diversity measures: Remote-clique, remote-star and remote-bipartition.
Our main result are polynomial time approximation schemes for these three diversification problems under the assumption that the metric space is doubling. This setting has been discussed in the recent literature. The existence of such a PTAS however was left open.
Our results also hold in the setting where the distances are raised to a fixed power q >= 1, giving rise to more variants of diversity functions, similar in spirit to the variations of clustering problems depending on the power applied to the pairwise distances. Finally, we provide a proof of NP-hardness for remote-clique with squared distances in doubling metric spaces.
BibTeX - Entry
@InProceedings{cevallos_et_al:LIPIcs:2018:9981,
author = {Alfonso Cevallos and Friedrich Eisenbrand and Sarah Morell},
title = {{Diversity Maximization in Doubling Metrics}},
booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)},
pages = {33:1--33:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-094-1},
ISSN = {1868-8969},
year = {2018},
volume = {123},
editor = {Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9981},
URN = {urn:nbn:de:0030-drops-99818},
doi = {10.4230/LIPIcs.ISAAC.2018.33},
annote = {Keywords: Remote-clique, remote-star, remote-bipartition, doubling dimension, grid rounding, epsilon-nets, polynomial time approximation scheme, facility locati}
}
|
Keywords: |
|
Remote-clique, remote-star, remote-bipartition, doubling dimension, grid rounding, epsilon-nets, polynomial time approximation scheme, facility locati |
|
Collection: |
|
29th International Symposium on Algorithms and Computation (ISAAC 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
06.12.2018 |
