Regularized nonmonotone submodular maximization

References

• Kempe D, Kleinberg J, Tardos É. Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining; 2003. p. 137–146.
   Google Scholar
• Krause A, Guestrin C. Near-optimal observation selection using submodular functions. In: AAAI; Vol. 7; 2007. p. 1650–1654.
   Google Scholar
• Lin H, Bilmes J. Multi-document summarization via budgeted maximization of submodular functions. In: Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics; 2010. p. 912–920.
   Google Scholar
• Lehmann B, Lehmann D, Nisan N. Combinatorial auctions with decreasing marginal utilities. Games Econ Behav. 2006;55(2):270–296.
   Web of Science ®Google Scholar
• Vondrák J. Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing; 2008. p. 67–74.
   Google Scholar
• Grötschel M, Lovász L, Schrijver A. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica. 1981;1(2):169–197.
   Web of Science ®Google Scholar
• Schrijver A. A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J Comb Theory Ser B. 2000;80(2):346–355.
   Web of Science ®Google Scholar
• Iwata S, Fleischer L, Fujishige S. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J ACM. 2001;48(4):761–777.
   Web of Science ®Google Scholar
• Feige U. A threshold of ln n for approximating set cover. J ACM. 1998;45(4):634–652.
   Web of Science ®Google Scholar
• Krause A, Guestrin CE. Near-optimal nonmyopic value of information in graphical models; 2012. arXiv preprint arXiv:12071394.
   Google Scholar
• Nikolakaki SM, Ene A, Terzi E. An efficient framework for balancing submodularity and cost. In: Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining; 2021. p. 1256–1266.
   Google Scholar
• Kazemi E, Minaee S, Feldman M, et al. Regularized submodular maximization at scale. In: International Conference on Machine Learning. PMLR; 2021. p. 5356–5366.
   Google Scholar
• Nemhauser GL, Wolsey LA, Fisher ML. An analysis of approximations for maximizing submodular set functions-i. Math Program. 1978;14(1):265–294.
   Web of Science ®Google Scholar
• Fisher ML, Nemhauser GL, Wolsey LA. An analysis of approximations for maximizing submodular set functions-II. In: Polyhedral combinatorics. Springer; 1978. p. 73–87.
   Google Scholar
• Nemhauser GL, Wolsey LA. Best algorithms for approximating the maximum of a submodular set function. Math Oper Res. 1978;3(3):177–188.
   Google Scholar
• Calinescu G, Chekuri C, Pal M, et al. Maximizing a monotone submodular function subject to a matroid constraint. SIAM J Comput. 2011;40(6):1740–1766.
   Web of Science ®Google Scholar
• Buchbinder N, Feldman M, Naor J, et al. Submodular maximization with cardinality constraints. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM; 2014. p. 1433–1452.
   Google Scholar
• Gharan SO, Vondrák J. Submodular maximization by simulated annealing. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM; 2011. p. 1098–1116.
   Google Scholar
• Feldman M, Naor J, Schwartz R. A unified continuous greedy algorithm for submodular maximization. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science. IEEE; 2011. p. 570–579.
   Google Scholar
• Buchbinder N, Feldman M, Seffi J, et al. A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J Comput. 2015;44(5):1384–1402.
   Web of Science ®Google Scholar
• Feige U, Mirrokni VS, Vondrák J. Maximizing non-monotone submodular functions. SIAM J Comput. 2011;40(4):1133–1153.
   Web of Science ®Google Scholar
• Sviridenko M, Vondrák J, Ward J. Optimal approximation for submodular and supermodular optimization with bounded curvature. Math Oper Res. 2017;42(4):1197–1218.
   Web of Science ®Google Scholar
• Feldman M. Guess free maximization of submodular and linear sums. Algorithmica. 2021;83(3):853–878.
   Web of Science ®Google Scholar
• Harshaw C, Feldman M, Ward J, et al. Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In: International Conference on Machine Learning. PMLR; 2019. p. 2634–2643.
   Google Scholar
• Vondrák J. Symmetry and approximability of submodular maximization problems. SIAM J Comput. 2013;42(1):265–304.
   Web of Science ®Google Scholar
• Alon N, Spencer JH. The probabilistic method. Hoboken, New Jersey: John Wiley & Sons; 2004.
   Google Scholar
• Mirzasoleiman B, Badanidiyuru A, Karbasi A, et al. Lazier than lazy greedy. In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 29; 2015.
   Google Scholar
• Buchbinder N, Feldman M, Schwartz R. Comparing apples and oranges: query trade-off in submodular maximization. Math Oper Res. 2017;42(2):308–329.
   Web of Science ®Google Scholar