Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification
Loading...
sydow-bigTriangle-ma14.pdf (269.59 KB)
Authors
Date
2014
Journal Title
Journal ISSN
Volume Title
Publisher
Polskie Towarzystwo Matematyczne
Using this material is possible in accordance with the relevant provisions of fair use or other exceptions provided by law. Other use requires the consent of the holder.
Abstract
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 un- derlying dissimilarity measure satisfies parameterised triangle inequality with pa- rameter α. The results apply to both relaxed and stronger variants of the triangle inequality. We also demonstrate potential applications of our findings in the result diversifica- tion problem including web search or entity summarisation in semantic knowledge graphs, as well as in practical computations on finite data sets.
Description
Keywords
Citation
M.Sydow, Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification, Mathematica Applicanda Vol. 42, no. 2, pp. 241-257, DOI: 10.14708/ma.v42i0.547, Print ISSN: 1730-2668; On-line ISSN: 2299-4009, Polish Mathematical Society, 2014