Cevallos, Alfonso ;
Eisenbrand, Friedrich ;
Zenklusen, Rico
MaxSum Diversity Via Convex Programming
Abstract
Diversity maximization is an important concept in information retrieval, computational geometry and operations research. Usually, it is a variant of the following problem: Given a ground set, constraints, and a function f that measures diversity of a subset, the task is to select a feasible subset S such that f(S) is maximized. The sumdispersion function f(S) which is the sum of the pairwise distances in S, is in this context a prominent diversification measure. The corresponding diversity maximization is the "maxsum" or "sumsum" diversification. Many recent results deal with the design of constantfactor approximation algorithms of diversification problems involving sumdispersion function under a matroid constraint.
In this paper, we present a PTAS for the maxsum diversity problem under a matroid constraint for distances d(.,.) of negative type. Distances of negative type are, for example, metric distances stemming from the l_2 and l_1 norms, as well as the cosine or spherical, or Jaccard distance which are popular similarity metrics in web and image search.
Our algorithm is based on techniques developed in geometric algorithms like metric embeddings and convex optimization. We show that one can compute a fractional solution of the usually nonconvex relaxation of the problem which yields an upper bound on the optimum integer solution. Starting from this fractional solution, we employ a deterministic rounding approach which only incurs a small loss in terms of objective, thus leading to a PTAS. This technique can be applied to other previously studied variants of the maxsum dispersion function, including combinations of diversity with linearscore maximization, improving over the previous constantfactor approximation algorithms.
BibTeX  Entry
@InProceedings{cevallos_et_al:LIPIcs:2016:5918,
author = {Alfonso Cevallos and Friedrich Eisenbrand and Rico Zenklusen},
title = {{MaxSum Diversity Via Convex Programming}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {26:126:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5918},
URN = {urn:nbn:de:0030drops59186},
doi = {10.4230/LIPIcs.SoCG.2016.26},
annote = {Keywords: Geometric Dispersion, Embeddings, Approximation Algorithms, Convex Programming, Matroids}
}
10.06.2016
Keywords: 

Geometric Dispersion, Embeddings, Approximation Algorithms, Convex Programming, Matroids 
Seminar: 

32nd International Symposium on Computational Geometry (SoCG 2016)

Issue date: 

2016 
Date of publication: 

10.06.2016 