Abstract
We study several questions related to diversifying search results. We give improved approximation algorithms in each of the following problems, together with some lower bounds.
1) We give a polynomialtime approximation scheme (PTAS) for a diversified search ranking problem [Nikhil Bansal et al., 2010] whose objective is to minimizes the discounted cumulative gain. Our PTAS runs in time n^{2^O(log(1/ε)/ε)} ⋅ m^O(1) where n denotes the number of elements in the databases and m denotes the number of constraints. Complementing this result, we show that no PTAS can run in time f(ε) ⋅ (nm)^{2^o(1/ε)} assuming GapETH and therefore our running time is nearly tight. Both our upper and lower bounds answer open questions from [Nikhil Bansal et al., 2010].
2) We next consider the MaxSum Dispersion problem, whose objective is to select k out of n elements from a database that maximizes the dispersion, which is defined as the sum of the pairwise distances under a given metric. We give a quasipolynomialtime approximation scheme (QPTAS) for the problem which runs in time n^{O_ε(log n)}. This improves upon previously known polynomialtime algorithms with approximate ratios 0.5 [Refael Hassin et al., 1997; Allan Borodin et al., 2017]. Furthermore, we observe that reductions from previous work rule out approximation schemes that run in n^õ_ε(log n) time assuming ETH.
3) Finally, we consider a generalization of MaxSum Dispersion called MaxSum Diversification. In addition to the sum of pairwise distance, the objective also includes another function f. For monotone submodular function f, we give a quasipolynomialtime algorithm with approximation ratio arbitrarily close to (11/e). This improves upon the best polynomialtime algorithm which has approximation ratio 0.5 [Allan Borodin et al., 2017]. Furthermore, the (11/e) factor is also tight as achieving betterthan(11/e) approximation is NPhard [Uriel Feige, 1998].
BibTeX  Entry
@InProceedings{abboud_et_al:LIPIcs.ICALP.2022.7,
author = {Abboud, Amir and CohenAddad, Vincent and Lee, Euiwoong and Manurangsi, Pasin},
title = {{Improved Approximation Algorithms and Lower Bounds for SearchDiversification Problems}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {7:17:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16348},
URN = {urn:nbn:de:0030drops163481},
doi = {10.4230/LIPIcs.ICALP.2022.7},
annote = {Keywords: Approximation Algorithms, Complexity, Data Mining, Diversification}
}
Keywords: 

Approximation Algorithms, Complexity, Data Mining, Diversification 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 