Improved Approximation Guarantee for Max Sum Diversification with Parameterised Triangle Inequality

摘要

We present improved 2/α approximation guarantee for the problem of selecting diverse set of p items when its formulation is based on Max Sum Facility Dispersion problem and the underlying dissimilarity measure satisfies parameterised triangle inequality with parameter α. Diversity-aware approach is gaining interest in many important applications such as web search, recommendation, database querying or summarisation, especially in the context of ambiguous user query or unknown user profile. In addition, we make some observations on the applicability of these results in practical computations on real data and link to important recent applications in the result diversification problem in web search and semantic graph summarisation. The results apply to both relaxed and strengthen variants of the triangle inequality.