Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification
Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification
复制标题
参数化三角形不等式的最大和和最大最小设施分散的近似保证及其在结果多样化中的应用
DOI：
10.14708/ma.v42i2.547
复制
发表时间：
2015
影响因子：
--
通讯作者：
M. Sydow
中科院分区：
文献类型：
--
作者：
M. Sydow
最初在运营研究中研究的设施分散问题最近发现了信息科学中结果多元化方法的重要新应用。此优化问题包括从一大批候选人中选择一小部分P项目，以最大化给定的目标函数。该函数表达了一组选定项目的分散概念。在大多数已知的配方中，问题是NP- hard，但是如果距离满足三角形不等式，则存在2-辅助算法。我们在两个最常见的变体中提供了通用2 =设施分散问题的近似保证：最大总和和最大最小值，当基础差异量度满足参数化的三角形不平等与参数时。结果适用于三角形不等式的松弛和增强变体。我们还证明了我们发现的潜在应用在结果多元化问题中，包括语义知识图中的Web搜索或实体摘要以及有限数据集的实际计算中。
Facility Dispersion Problem, originally studied in Operations Research, has recently found important new applications in Result Diversification approach in information sciences. This optimisation problem consists of selecting a small set of p items out of a large set of candidates to maximise a given objective function. The function expresses the notion of dispersion of a set of selected items in terms of a pair-wise distance measure between items. In most known formulations the problem is NP-hard, but there exist 2-approximation algorithms for some cases if distance satisfies triangle inequality. We present generalised 2= approximation guarantees for the Facility Dispersion Problem in its two most common variants: Max Sum and Max Min, when the underlying dissimilarity measure satisfies parameterised triangle inequality with parameter . The results apply to both relaxed and strengthen variants of the triangle inequality. We also demonstrate potential applications of our findings in the result diversification problem including web search or entity summarisation in semantic knowledge graphs, as well as in practical computations on finite data sets.