论文标题
改进了近似算法和下限，以解决搜索多元化问题
Improved Approximation Algorithms and Lower Bounds for Search-Diversification Problems
论文作者
论文摘要
我们研究了几个与多元化搜索结果有关的问题。我们在以下每个问题中提供了改进的近似算法，以及一些下限。 - 我们为多元化的搜索排名问题提供了多项式时间近似方案（PTA）[Bansal等，ICALP 2010]，其目标是最大程度地减少累积累积增益。我们的PTA在时间上运行$ n^{2^{o（\ log（1/ε）/ε）}}} \ cdot m^{o（1）} $，其中$ n $表示数据库中元素的数量。补充这一点，我们表明，没有PTA可以在时间$ f（ε）\ cdot（nm）^{2^{o（1/ε）}} $上运行，假设gap-eth;因此，我们的运行时间几乎很紧。我们的两个界限都回答了Bansal等人的开放问题。 - 我们接下来考虑最大化分散问题，其目标是从$ n $元素中选择$ k $，以最大化分散体，该元素定义为给定度量下的成对距离的总和。我们为问题$ n^{o_ε（\ log n）} $提供了一个quasipolynomial时间近似方案。这改善了先前已知的多项式时间算法，比率为0.5 [Hassin等，Oper。 res。 Lett。 1997; Borodin等，ACM Trans。算法2017]。此外，我们观察到，已知的减排排除了以$ n^{\ tilde {o}_ε（\ log n）} $ time为eth的近似方案。 - 我们考虑了称为Max-sum多样化的最大和分散体的概括。除了成对距离之外，该目标还包括另一个功能$ f $。对于单调性少量$ f $，我们给出了一个近似值算法的准时时间算法，任意接近$（1-1/e）$。这可以改善Borodin等人的近似值$ 0.5 $的最佳多项式算法。此外，$（1-1/e）$因素紧张，因为取得比$（1-1/e）$近似是NP-Hard [Feige，J。Acm 1998]。
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. - We give a polynomial-time approximation scheme (PTAS) for a diversified search ranking problem [Bansal et al., ICALP 2010] whose objective is to minimizes the discounted cumulative gain. Our PTAS runs in time $n^{2^{O(\log(1/ε)/ε)}} \cdot m^{O(1)}$ where $n$ denotes the number of elements in the databases. Complementing this, we show that no PTAS can run in time $f(ε) \cdot (nm)^{2^{o(1/ε)}}$ assuming Gap-ETH; therefore our running time is nearly tight. Both of our bounds answer open questions of Bansal et al. - We next consider the Max-Sum Dispersion problem, whose objective is to select $k$ out of $n$ elements that maximizes the dispersion, which is defined as the sum of the pairwise distances under a given metric. We give a quasipolynomial-time approximation scheme for the problem which runs in time $n^{O_ε(\log n)}$. This improves upon previously known polynomial-time algorithms with approximate ratios 0.5 [Hassin et al., Oper. Res. Lett. 1997; Borodin et al., ACM Trans. Algorithms 2017]. Furthermore, we observe that known reductions rule out approximation schemes that run in $n^{\tilde{o}_ε(\log n)}$ time assuming ETH. - We consider a generalization of Max-Sum Dispersion called Max-Sum Diversification. In addition to the sum of pairwise distance, the objective includes another function $f$. For monotone submodular $f$, we give a quasipolynomial-time algorithm with approximation ratio arbitrarily close to $(1 - 1/e)$. This improves upon the best polynomial-time algorithm which has approximation ratio $0.5$ by Borodin et al. Furthermore, the $(1 - 1/e)$ factor is tight as achieving better-than-$(1 - 1/e)$ approximation is NP-hard [Feige, J. ACM 1998].
