{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:02:57Z","timestamp":1775815377570,"version":"3.50.1"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2017,7,13]],"date-time":"2017-07-13T00:00:00Z","timestamp":1499904000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSERC Discovery","award":["RGPIN-2017-06551"],"award-info":[{"award-number":["RGPIN-2017-06551"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2017,7,31]]},"abstract":"<jats:p>\n            Result diversification is an important aspect in web-based search, document summarization, facility location, portfolio management, and other applications. Given a set of ranked results for a set of objects (e.g., web documents, facilities, etc.) with a distance between any pair, the goal is to select a subset\n            <jats:italic>S<\/jats:italic>\n            satisfying the following three criteria: (a) the subset\n            <jats:italic>S<\/jats:italic>\n            satisfies some constraint (e.g., bounded cardinality), (b) the subset contains results of high \u201cquality,\u201d and (c) the subset contains results that are \u201cdiverse\u201d relative to the distance measure. The goal of result diversification is to produce a diversified subset while maintaining high quality as much as possible. We study a broad class of problems where the distances are a metric, where the constraint is given by independence in a matroid, where quality is determined by a monotone submodular function and diversity is defined as the sum of distances between objects in\n            <jats:italic>S<\/jats:italic>\n            . Our problem is a generalization of the\n            <jats:italic>max-sum diversification<\/jats:italic>\n            problem studied in Gollapudi and Sharma [2009], which in turn is a generalization of the\n            <jats:italic>max-sum p-dispersion problem<\/jats:italic>\n            studied extensively in location theory. It is NP-hard even with the triangle inequality. We propose two simple and natural algorithms: a greedy algorithm for a cardinality constraint and a local search algorithm for an arbitrary matroid constraint. We prove that both algorithms achieve constant approximation ratios.\n          <\/jats:p>","DOI":"10.1145\/3086464","type":"journal-article","created":{"date-parts":[[2017,7,13]],"date-time":"2017-07-13T13:44:03Z","timestamp":1499953443000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":33,"title":["Max-Sum Diversification, Monotone Submodular Functions, and Dynamic Updates"],"prefix":"10.1145","volume":"13","author":[{"given":"Allan","family":"Borodin","sequence":"first","affiliation":[{"name":"University of Toronto, Ontario, Canada"}]},{"given":"Aadhar","family":"Jain","sequence":"additional","affiliation":[{"name":"Under Armour Connected Fitness, Mountain View, California"}]},{"given":"Hyun Chul","family":"Lee","sequence":"additional","affiliation":[{"name":"Under Armour Connected Fitness, Mountain View, California"}]},{"given":"Yuli","family":"Ye","sequence":"additional","affiliation":[{"name":"Wish, Ontario, Canada"}]}],"member":"320","published-online":{"date-parts":[[2017,7,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487636"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1498759.1498766"},{"key":"e_1_2_1_3_1","unstructured":"Noga Alon. 2014. (2014). Personal communication.  Noga Alon. 2014. (2014). Personal communication."},{"key":"e_1_2_1_4_1","unstructured":"Noga Alon Sanjeev Arora Rajsekar Manoikaran Dana Moshkovitz and Omri Weinstein. 2011. Inapproximability of densest &kappa;-subgraph from aveage case hardness. (2011). Unpublished manuscript.  Noga Alon Sanjeev Arora Rajsekar Manoikaran Dana Moshkovitz and Omri Weinstein. 2011. Inapproximability of densest &kappa;-subgraph from aveage case hardness. (2011). Unpublished manuscript."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14162-1_23"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9142-2"},{"key":"e_1_2_1_7_1","unstructured":"Alan Borodin Dai Le and Yuli Ye. 2014. Weakly submodular functions. CoRR abs\/1401.6697 (2014).  Alan Borodin Dai Le and Yuli Ye. 2014. Weakly submodular functions. CoRR abs\/1401.6697 (2014)."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213580"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935872"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1017\/S000497270004140X"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/290941.291025"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-61422-2_120"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1145"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1148170.1148245"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(00)00058-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835449.1835506"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935897"},{"key":"e_1_2_1_19_1","first-page":"49","article-title":"Diversity over continuous data","volume":"32","author":"Drosou Marina","year":"2009","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1860702.1860709"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(90)90297-O"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(89)90420-7"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-003-1074-x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0121195"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526761"},{"key":"e_1_2_1_26_1","volume-title":"Symposium on Discrete Algorithms. 150--159","author":"Halld\u00f3rsson Magn\u00fas M.","year":"1995"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(97)00034-5"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795286612"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705447037"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.1987.tb00133.x"},{"key":"e_1_2_1_32_1","volume-title":"Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics\/Human Language Technologies (NAACL\/HLT\u201910)","author":"Lin Hui","year":"2010"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics\/Human Language Technology Conference (NAACL\/HLT\u201911)","author":"Lin Hui","year":"2011"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASRU.2009.5373486"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687663"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746600"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009996"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01588971"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10791-009-9123-y"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390255"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772770"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.42.2.299"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2009916.2009997"},{"key":"e_1_2_1_44_1","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency","author":"Schrijver Alexander","year":"2003"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of the International Conference on Machine Learning (ICML\u201910)","author":"Slivkins Aleksandrs","year":"2010"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08326-1_60"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","first-page":"1395","DOI":"10.14778\/3402755.3402779","article-title":"DivDB: A system for diversifying query results","volume":"4","author":"Vieira Marcos R.","year":"2011","journal-title":"Proc. VLDB"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767846"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90174-3"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/1516360.1516404"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390310"},{"key":"e_1_2_1_53_1","unstructured":"Sepehr Abbasi Zadeh and Mehrdad Ghadiri. 2015. Max-sum diversification monotone submodular functions and semi-metric spaces. CoRR abs\/1511.02402 (2015).  Sepehr Abbasi Zadeh and Mehrdad Ghadiri. 2015. Max-sum diversification monotone submodular functions and semi-metric spaces. CoRR abs\/1511.02402 (2015)."},{"key":"e_1_2_1_54_1","volume-title":"Proceedings of the 31st AAAI Conference on Artificial Intelligence. 2876--2883","author":"Zadeh Sepehr Abbasi","year":"2017"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/860435.860440"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.14778\/3402755.3402769","article-title":"BROAD: Diversified keyword search in databases","volume":"4","author":"Zhao Feng","year":"2011","journal-title":"Proc. VLDB"},{"key":"e_1_2_1_57_1","volume-title":"Proceedings of the Conference of the North American Chapter of the Association for Computational Linguistics\/Human Language Technologies (NAACL\/HLT\u201907)","author":"Zhu Xiaojin","year":"2007"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3086464","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3086464","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:37:01Z","timestamp":1750217821000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3086464"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,7,13]]},"references-count":57,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2017,7,31]]}},"alternative-id":["10.1145\/3086464"],"URL":"https:\/\/doi.org\/10.1145\/3086464","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,7,13]]},"assertion":[{"value":"2015-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}