Linear Relaxations for Finding Diverse Elements in Metric Spaces
Choosing a diverse subset of a large collection of points in a metric space is a fundamental problem, with applications in feature selection, recommender systems, web search, data summarization, etc. Various notions of diversity have been proposed, tailored to different applications. The general algorithmic goal is to find a subset of points that maximize diversity, while obeying a cardinality (or more generally, matroid) constraint. The goal of this paper is to develop a novel linear programming (LP) framework that allows us to design approximation algorithms for such problems. We study an objective known as sum-min diversity, which is known to be effective in many applications, and give the first constant factor approximation algorithm. Our LP framework allows us to easily incorporate additional constraints, as well as secondary objectives. We also prove a hardness result for two natural diversity objectives, under the so-called planted clique assumption. Finally, we study the empirical performance of our algorithm on several standard datasets. We first study the approximation quality of the algorithm by comparing with the LP objective. Then, we compare the quality of the solutions produced by our method with other popular diversity maximization algorithms.
The paper considers the problem of selecting M diverse elements of a finite set, given that those are elements of a metric space and therefore a distance between elements is defined. More precisely, the work focuses on the so called 'sum-min diversity', which has attractive practical properties. The problem of finding the M-tuple of diverse points with respect to such measure is known to be NP-hard and the best known algorithm provides an approximation factor of O(1/log n), where n is the size of the set. Authors propose a linear programing approximation of the problem and a probabilistic rounding procedure to obtain a binary vector defining the diverse M-tuple. The expected output of this probabilistic algorithm provides a constant factor approximate solution for the problem.
Although the provided novel algorithm looks impressive both from the theoretical prospective and in the experimental comparison, its substantiation has quite some room for improvement.  The major point is the proof of Theorem 1:  - it is unclear how the proof of the theorem follows from Lemmas 3 and 4, since none of these lemmas is related to the optimal solution of the considered diversity problem. I assume that the missing proposition is the one, which would establish connection between the considered linear program in lines 153-154 (by the way, it is very uncomfortable that the main formulation is not numbered and therefore can not be easily referenced) and the diversity problem. I believe that this connection may have the following format: if the linear program is equipped with integrality constraints (which is, all variables x_{ir}\in {0,1}), the resulting ILP is equivalent to the considered diversity problem. Indeed, the proof of such a proposition is not obvious for me as well.  Without clarification of this point I would assume a major flaw in the proof and, therefore, absence of a theoretical contribution.  == post-rebuttal update==  The authors addressed my main issue - the proof of Theorem 1. Although I agree to R7 about experimental evaluation, I believe the paper can be accepted provided that the mentioned experimental comparison is included into the paper.