Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification
dc.contributor.author | Sydow, Marcin | |
dc.date.accessioned | 2015-04-24T07:19:53Z | |
dc.date.available | 2015-04-24T07:19:53Z | |
dc.date.issued | 2014 | |
dc.identifier.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 | pl_PL |
dc.identifier.issn | 1730-2668 | |
dc.identifier.uri | https://depot.ceon.pl/handle/123456789/6671 | |
dc.description.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. | pl_PL |
dc.language.iso | en | pl_PL |
dc.publisher | Polskie Towarzystwo Matematyczne | pl_PL |
dc.rights | Dozwolony użytek | |
dc.subject | parameterised triangle inequality | pl_PL |
dc.subject | approx- imation algorithms | pl_PL |
dc.subject | max sum and max min facility dispersion | pl_PL |
dc.subject | diversity | pl_PL |
dc.title | Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification | pl_PL |
dc.type | info:eu-repo/semantics/article | pl_PL |
dc.contributor.organization | Polish Academy of Sciences | pl_PL |
dc.contributor.organization | Polsko-Japońska Akademia Technik Komputerowych | |
dc.description.eperson | marcin sydow |
Pliki tej pozycji
Pozycja umieszczona jest w następujących kolekcjach
-
Artykuły / Articles [16158]
Korzystanie z tego materiału jest możliwe zgodnie z właściwymi przepisami o dozwolonym użytku lub o innych wyjątkach przewidzianych w przepisach prawa, a korzystanie w szerszym zakresie wymaga uzyskania zgody uprawnionego.