Abboud, Amir ;
CohenAddad, Vincent ;
Lee, Euiwoong ;
Manurangsi, Pasin
Improved Approximation Algorithms and Lower Bounds for SearchDiversification Problems
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}
}
28.06.2022
Keywords: 

Approximation Algorithms, Complexity, Data Mining, Diversification 
Seminar: 

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

Issue date: 

2022 
Date of publication: 

28.06.2022 