Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification
MetadataShow full item record
mailto:?subject=I recommend a publication at CeON Repository&body=I recommend a publication “Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification” available at CeON Repository [https://depot.ceon.pl/handle/123456789/6671]. Recommend
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.
- Artykuły / Articles 
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.