PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 42 | 2 |
Tytuł artykułu

Approximation Guarantees for Max Sum and Max Min Facility Dispersion with Parameterised Triangle Inequality and Applications in Result Diversification

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
PL
Problem "Facility Dispersion", pierwotnie studiowany w badaniach operacyjnych, znajduje od niedawna nowe ważne zastosowania w podejściu polegającym na dywersyfikacji wyników w naukach informacyjnych.Jest to problem optymalizacji dyskretnej polegający na wyborze niewielkiego zbioru p elementów z pewnego dużego zbioru kandydatów tak, aby zmaksymalizować pewną funkcję celu. Funkcja ta wyraża "rozproszenie" wybranych elementów, za pośrednictwem pomocnicznej miary odległości par elementów.Problem jest NP-trudny w większości znanych wariantów, lecz istnieją algorytmy aproksymacyjne o współczynniku 2 dla niektórych z nich, gdy miara odległości jest metryką.W artykule zaprezentowano twierdzenia, które uogólniają znane wyniki do przypadku gdy miara odległości spełnia parametryzowaną nierówność trójkąta z parametrem alfa, dla wariantów "Max Sum" oraz "Max Min" problemu. Wyniki dotyczą zarówno osłabionej jak i wzmocnionej nierówności trójkąta.Zademonstrowano także potencjalne zastosowania powyższych rezultatów w problemie dywersyfikacji wyników w takich dziedzinach jak wyszukiwanie informacji czy podsumowania encyj w semantycznych grafach wiedzy, jak również w praktycznych obliczeniach na skończonych zbiorach danych.
EN
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-approximationalgorithms 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.
Rocznik
Tom
42
Numer
2
Opis fizyczny
Daty
wydano
2014
online
2014-09-07
Twórcy
autor
Bibliografia
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.ojs-doi-10_14708_ma_v42i2_547
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.