An Improved Analysis of Local Search for Max-Sum Diversification

References

• [1] Abbassi Z, Mirrokni VS, Thakur M (2013) Diversity maximization under matroid constraints. Proc. 19th ACM Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 32–40.Crossref, Google Scholar
• [2] Alon N, Arora S, Manokaran R, Moshkovitz D, Weinstein O (2011) Inapproximability of densest \kappa-subgraph from average case hardness. Working paper, Princeton University, Princeton, NJ.Google Scholar
• [3] Bhattacharya S, Gollapudi S, Munagala K (2011) Consideration set generation in commerce search. Proc. 20th Internat. Conf. World Wide Web (ACM, New York), 317–326.Crossref, Google Scholar
• [4] Birnbaum B, Goldman KJ (2009) An improved analysis for a greedy remote-clique algorithm using factor-revealing LPs. Algorithmica 55(1):42–59.Crossref, Google Scholar
• [5] Borodin A, Lee HC, Ye Y (2012) Max-sum diversification, monotone submodular functions and dynamic updates. Proc. 31st Sympos. Principles Database Systems (ACM, New York), 155–166.Crossref, Google Scholar
• [6] Brualdi RA (1969) Comments on bases in dependence structures. Bull. Australian Math. Soc. 1(02):161–167.Crossref, Google Scholar
• [7] Ceccarello M, Pietracaprina A, Pucci G, Upfal E (2017) Mapreduce and streaming algorithms for diversity maximization in metric spaces of bounded doubling dimension. Proc. VLDB Endowment 10(5):469–480.Crossref, Google Scholar
• [8] Cevallos A, Eisenbrand F, Zenklusen R (2016) Max-sum diversity via convex programming. Sándor Fekete and Anna Lubiw, eds. Proc. 32nd Sympos. Comput. Geometry, Leibniz International Proceedings in Informatics (LIPIcs), vol. 51 (Schloss Dagstuhl-Leibniz Zentrum für Informatik, Dagstuhl, Germany), 26:1–14.Google Scholar
• [9] Cevallos A, Eisenbrand F, Zenklusen R (2017) Local search for max-sum diversification. Proc. 28th Sympos. Discrete Algorithms (SIAM, Philadelphia), 130–142.Crossref, Google Scholar
• [10] Charikar MS (2002) Similarity estimation techniques from rounding algorithms. Proc. 34th Annual ACM Sympos. Theory Comput. (ACM, New York), 380–388.Crossref, Google Scholar
• [11] Chekuri C, Vondrák J, Zenklusen R (2010) Dependent randomized rounding via exchange properties of combinatorial structures. Proc. 51st IEEE Sympos. Foundations Comput. Sci. (IEEE, New York), 575–584.Crossref, Google Scholar
• [12] Chekuri C, Vondrák J, Zenklusen R (2011) Multi-budgeted matchings and matroid intersection via dependent rounding. Proc. 21st Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 1080–1097.Crossref, Google Scholar
• [13] Conforti M, Cornuéjols G (1984) Submodular set functions, matroids and the greedy algorithm: Tight worst-case bounds and some generalizations of the Rado-Edmonds theorem. Discrete Appl. Math. 7(3):251–274.Crossref, Google Scholar
• [14] Deza MM, Laurent M (1997) Geometry of Cuts and Metrics (Springer-Verlag, Berlin).Crossref, Google Scholar
• [15] Deza MM, Maehara H (1990) Metric transforms and euclidean embeddings. Trans. Amer. Math. Soc. 317(2):661–671.Crossref, Google Scholar
• [16] Feige U (1998) A threshold of \ln n for approximating set cover. J. ACM 45(4):634–652.Crossref, Google Scholar
• [17] Fekete SP, Meijer H (2004) Maximum dispersion and geometric maximum weight cliques. Algorithmica 38(3):501–511.Crossref, Google Scholar
• [18] Filmus Y, Ward J (2014) Monotone submodular maximization over a matroid via non-oblivious local search. SIAM J. Comput. 43(2):514–542.Crossref, Google Scholar
• [19] Gollapudi S, Sharma A (2009) An axiomatic approach for result diversification. Proc. 18th Internat. Conf. World Wide Web (ACM, New York), 381–390.Crossref, Google Scholar
• [20] Hassin R, Rubinstein S, Tamir A (1997) Approximation algorithms for maximum dispersion. Oper. Res. Lett. 21(3):133–137.Crossref, Google Scholar
• [21] Indyk P, Mahabadi S, Mahdian M, Mirrokni VS (2014) Composable core-sets for diversity and coverage maximization. Proc. 33rd ACM Sympos. Principles Database Systems (ACM, New York), 100–108.Crossref, Google Scholar
• [22] Lee J, Sviridenko M, Vondrák J (2010) Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res. 35(4):795–806.Link, Google Scholar
• [23] Manning CD, Raghavan P, Schütze H (2008) Introduction to Information Retrieval (Cambridge University Press, Cambridge, UK), vol. 1.Crossref, Google Scholar
• [24] Nemhauser GL, Wolsey LA (1978) Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3):177–188.Link, Google Scholar
• [25] Nikolov A (2015) Randomized rounding for the largest simplex problem. Proc. 47th Annual ACM Sympos. Theory Comput. (ACM, New York), 861–870.Crossref, Google Scholar
• [26] Pekalska E, Duin RPW (2005) The Dissimilarity Representation for Pattern Recognition: Foundations And Applications (Machine Perception and Artificial Intelligence) (World Scientific Publishing Co., Inc., River Edge, NJ).Crossref, Google Scholar
• [27] Ravi SS, Rosenkrantz DJ, Tayi GK (1994) Heuristic and special case algorithms for dispersion problems. Oper. Res. 42(2):299–310.Link, Google Scholar
• [28] Salton G, MacGill MJ (1983) Introduction to Modern Information Retrieval (McGraw-Hill, New York).Google Scholar
• [29] Schoenberg IJ (1938) Metric spaces and completely monotone functions. Ann. Math. 39(4):811–841.Crossref, Google Scholar
• [30] Schoenberg IJ (1938) Metric spaces and positive definite functions. Trans. Amer. Math. Soc. 44(3):522–536.Crossref, Google Scholar
• [31] Schrijver A (2003) Combinatorial Optimization—Polyhedra and Efficiency (Springer Science & Business Media, New York).Google Scholar
• [32] Sviridenko M, Vondrák J, Ward J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper. Res. 42(4):1197–1218.Link, Google Scholar