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

• Autorzy: Sydow M.

Identyfikatory

DOI

10.14708/ma.v42i2.547

Warianty tytułu

PL

Gwarancje współczynnika aproksymacji dla problemów Max Sum (i Max Min) Facility Dispersion z parametryzowaną nierównością trójkąta i zastosowania w dywersyfikacji wyników

• Języki publikacji: EN

Abstrakty

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-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 underlying dissimilarity measure satisfies parameterised triangle inequality with parameter α. The results apply to both relaxed and stronger 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.

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.

Słowa kluczowe

EN

diversity; max sum; max min facility dispersion; approximation algorithms; parameterised triangle inequality

PL

dywersyfikacja; problem dyspersji; parametryzowana nierówność trójkąta

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Mathematica Applicanda
• Rocznik: 2014
• Tom: Vol. 42, No. 2
• Strony: 241--257
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Sydow M.

• Polish Academy of Science Institute of Computer Science, Ordona 21, 01-237 Warszawa, Poland
• Polish-Japanese Institute of Information Technology Web Mining Lab, Koszykowa 86, 02-008 Warszawa, Poland

Bibliografia

• [1] Thomas Andreae and Hans-Jurgen Bandelt. Performance guarantees for approximation algorithms depending on parametrized triangle inequalities. SIAM Journal of Discrete Mathematics, 8:1-16, 1995. doi: 10.1137/S0895480192240226
• [2] Michael A. Bender and Chandra Chekuri. Performance guarantees for the tsp with a parameterized triangle inequality. Information Processing , 73(1-2):17 —21, 2000. doi:10.1016/S0020-0190(99)00160-X
• [3] Markus Blaser. An improved approximation algorithm for the asymmetric tsp with strengthened triangle inequality In Automata, Languages and Programming, volume 2719 of Lecture Notes in Computer Science, JosC.M. Baeten, JanKarel Lenstra, Joachim Parrow, and GerhardJ. Woeginger, eds., pages 157—163. Springer Berlin Heidelberg, 2003. doi: 10.1016/j.jda.2005.07.004
• [4] Hans-Joachim Bockenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, and Walter Unger. Approximation algorithms for the TSP with sharpened triangle inequality. Information Processing Letters, 75(3):133 — 138, 2000. doi: 10.1016/S0020-0190(00)00089-2
• [5] Hans-Joachim Bockenhauer, Tobias Momke, and Monika Steinov'a. Improved approximations for tsp with simple precedence constraints. J. of Discrete Algorithms, 21:32—40, 2013. doi: 10.1016/j.jda.2013.04.002
• [6] Allan Borodin, Hyun Chul Lee, and Yuli Ye. Max-sum diversification, monotone submod- ular functions and dynamic updates In Proceedings of the 31st symposium on Principles of Database Systems, PODS ’12, pages 155—166, New York, NY, USA, 2012. ACM. doi: 10.1145/2213556.2213580
• [7] Barun Chandra and Magnus M. Halldorsson. Facility dispersion and remote subgraphs In Algorithm Theory - SWAT’96, volume 1097 of Lecture Notes in Computer Science, Rolf Karlsson and Andrzej Lingas, eds, pages 53—65. Springer Berlin Heidelberg, 1996. doi: 10.1007/3-540-61422-2_120
• [8] Barun Chandra and Magnus M Halldorsson. Approximation algorithms for dispersion problems. Journal of Algorithms, 38(2):438 — 465, 2001. doi: 10.1006/jagm.2000.1145
• [9] Erhan Erkut. The discrete p-dispersion problem. European Journal of Operational Research, 46(1):48 — 60, 1990. doi: 10.1016/0377-2217(90)90297-0
• [10] Ronald Fagin and Larry Stockmeyer. Relaxing the triangle inequality in pattern matching. Int. J. Comput. Vision, 30(3):219—231, 1998. doi: 10.1023/A:1008023416823
• [11] Christopher L. Fleming, Stanley E. Griffis, and John E. Bell. The effects of triangle inequality on the vehicle routing problem. European Journal of Operational Research, 224(1):1 — 7, 2013. doi: 10.1016/j.ejor.2012.07.005
• [12] Sreenivas Gollapudi and Aneesh Sharma. An axiomatic approach for result diversification In Proceedings of the 18th international conference on World wide web, WWW ’09, pages 381-390, New York, NY, USA, 2009. ACM. doi: 10.1145/1526709.1526761
• [13] Teofilo F. Gonzalez. Handbook of approx. algorithms and metaheuristics. CRC Press, 2007. MR 2307955
• [14] Refael Hassin, Shlomi Rubinstein, and Arie Tamir. Approximation algorithms for maximum dispersion. Oper. Res. Lett., 21(3):133-137, 1997. doi: 10.1016/S0167-6377(97)00034-5
• [15] Witold Kosiński, Tomasz Kuśmierczyk, Pawel Rembelski, and Marcin Sydow. Application of ant-colony optimisation to compute diversified entity summarisation on semantic knowledge graphs In Proc. of International IEEE AAIA 2013/FedCSIS Conference, Annals of Computer Science and Information Systems, volume 1, pages 69-76, 2013.
• [16] S.S.Ravi, D.J.Rosenkrantz, and G.K.Tayi. Heuristic and special case algorithms for dispersion problems. Operations Research, 42(2):299-310, 1994. doi: 10.1287/opre.42.2.299
• [17] Marcin Sydow. Improved approximation guarantee for max sum diversification with pa- rameterised triangle inequality In Foundations of Intelligent Systems, volume 8502 of Lecture Notes in Computer Science, Troels Andreasen, Henning Christiansen, Juan-Carlos Cubero, and Zbigniew Ras, eds, pages 554-559. Springer International Publishing, 2014. doi: 10.1007/978-3-319-08326-1_60
• [18] Marcin Sydow, Mariusz Pikula, and Ralf Schenkel. The notion of diversity in graphical entity summarisation on semantic knowledge graphs. Journal of Intelligent Information Systems, 41:109-149, 2013. doi: 10.1007/s10844-013-0239-6
• [19] D. W. Wang and Yue-Sun Kuo. A study on two geometric location problems. Inf. Process. Lett., 28(6):281-286, August 1988. doi: 10.1016/0020-0190(88)90174-3