References(38)
[1]
H. Lin and J. Bilmes, A class of submodular functions for document summarization, in Proc. 49th Annu. Meeting of the Association for Computational Linguistics: Human Language Technologies, Portland, OR, USA, 2011, pp. 510–520.
[2]
D. Kempe, J. Kleinberg, and É. Tardos, Maximizing the spread of influence through a social network, in Proc. 9th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, Washington, DC, USA, 2003, pp. 137–146.
[3]
J. Lee, Encyclopedia of Environmetrics. New York, NY, USA: John Wiley & Sons, Ltd., 2006, pp. 1229–1234.
[4]
A. Badanidiyuru, B. Mirzasoleiman, A. Karbasi, and A. Krause, Streaming submodular maximization: Massive data summarization on the fly, in Proc. 20th ACM SIGKDD Int. Conf. Knowledge Discovery and Data Mining, New York, NY, USA, 2014, pp. 671–680.
[5]
T. Soma, N. Kakimura, K. Inaba, and K. Kawarabayashi, Optimal budget allocation: Theoretical guarantee and efficient algorithm, in Proc. 31st Int. Conf. Machine Learning, Beijing, China, 2014, pp. I-351–I-359.
[6]
E. Balkanski, A. Rubinstein, and Y. Singer, An exponential speedup in parallel running time for submodular maximization without loss in approximation, in Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms, San Diego, CA, USA, 2019, pp. 283–302.
[7]
C. Chekuri and K. Quanrud, Submodular function maximization in parallel via the multilinear relaxation, in Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms, San Diego, CA, USA, 2019, pp. 303–322.
[8]
A. Das, and D. Kempe, Algorithms for subset selection in linear regression, in Proc. 40th Annu. ACM Symp. Theory of Computing, Victoria, Canada, 2008, pp. 45–54.
[9]
A. Ene and H. L. Nguyen, Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time, in Proc. 30th Annu. ACM-SIAM Symp. Discrete Algorithms, San Diego, CA, USA, 2019, pp. 274–282.
[10]
A. Das and D. Kempe, Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection, in Proc. 28th Int. Conf. Machine Learning, Washington, DC, USA, 2011, pp. 1057–1064.
[11]
D. Golovin and A. Krause, Adaptive submodularity: Theory and applications in active learning and stochastic optimization, J. Artif. Intell. Res., vol. 42, no. 1, pp. 427–486, 2011.
[12]
S. Gong, Q. Nong, W. Liu, and Q. Fang, Parametric monotone function maximization with matroid constraints, J. Glob. Optim., vol. 75, no. 3, pp. 833–849, 2019.
[13]
C. Huang and N. Kakimura, Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint, in Proc. 16th Int. Symp. Algorithms and Data Structures, Edmonton, Canada, 2019, pp. 438–451.
[14]
A. Norouzi-Fard, J. Tarnawski, S. Mitrović, A. Zandieh, A. Mousavifar, and O. Svensson, Beyond 1/2-approximation for submodular maximization on massive data streams, in Proc. 35th Int. Conf. Machine Learning, Stockholm, Sweden, 2018, pp. 3829–3838.
[15]
A. Shioura, On the pipage rounding algorithm for submodular function maximization—a view from discrete convex analysis, Discrete Math. Algorithms Appl., vol. 1, no. 1, pp. 1–23, 2009.
[16]
R. Q. Yang, D. C. Xu, Y. J. Jiang, Y. S. Wang, and D. M. Zhang, Approximating robust parameterized submodular function maximization in large-scales, Asia Pac. J. Oper. Res., vol. 36, no. 4, p. 1950022, 2019.
[17]
G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, An analysis of approximations for maximizing submodular set functions-I, Math. Program., vol. 14, no. 1, pp. 265–294, 1978.
[18]
U. Feige, A threshold of ln n for approximating set cover, J. ACM, vol. 45, no. 4, pp. 634–652, 1998.
[19]
M. Sviridenko, A note on maximizing a submodular set function subject to a knapsack constraint, Oper. Res. Lett., vol. 32, no. 1, pp. 41–43, 2004.
[20]
G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák, Maximizing a monotone submodular function subject to a matroid constraint, SIAM J. Comput., vol. 40, no. 6, pp. 1740–1766, 2011.
[21]
A. Krause, J. Leskovec, C. Guestrin, J. VanBriesen, and C. Faloutsos, Efficient sensor placement optimization for securing large water distribution networks, J. Water Resour. Plann. Manage., vol. 134, no. 6, pp. 516–526, 2008.
[22]
M. Kapralov, I. Post, and J. Vondrák, Online submodular welfare maximization: Greedy is optimal, in Proc. 24th Annu. ACM-SIAM Symp. Discrete Algorithms, New Orleans, LA, US, 2013, pp. 1216–1225.
[23]
R. Khanna, E. R. Elenberg, A. G. Dimakis, S. Negahban, and J. Ghosh, Scalable greedy feature selection via weak submodularity, in Proc. 20th Int. Conf. Artificial Intelligence and Security, Fort Lauderdale, FL, USA, 2017, pp. 1560–1568.
[24]
N. Lawrence, M. Seeger, and R. Herbrich, Fast sparse Gaussian process methods: The informative vector machine, in Proc. 15th Int. Conf. Neural Information Processing Systems, Cambridge, MA, USA, 2002, pp. 625–632.
[25]
Y. Lin, W. Chen, and J. C. S. Lui, Boosting information spread: An algorithmic approach, in Proc. of the 2017 IEEE 33rd Int. Conf. Data Engineering, San Diego, CA, USA, 2017, pp. 883–894.
[26]
T. Soma and Y. Yoshida, A generalization of submodular cover via the diminishing return property on the integer lattice, in Proc. 28th Int. Conf. Neural Information Processing Systems, Montreal, Canada, 2015, pp. 847–855.
[27]
L. A. Wolsey, Maximising real-valued submodular functions: Primal and dual heuristics for location problems, Math. Oper. Res., vol. 7, no. 3, pp. 410–425, 1982.
[28]
X. Zhu, J. Yu, W. Lee, D. Kim, S. Shan, and D. Z. Du, New dominating sets in social networks, J. Glob. Optim., vol. 48, no. 4, pp. 633–642, 2010.
[29]
A. Krause, A. Singh, and C. Guestrin, Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies, J. Mach. Learn. Res., vol. 9, pp. 235–284, 2008.
[30]
A. A. Bian, J. M. Buhmann, A. Krause, and S. Tschiatschek, Guarantees for Greedy maximization of non-submodular functions with applications, in Proc. 34th Int. Conf. Machine Learning, Sydney, Australia, 2017, pp. 498–507.
[31]
I. Bogunovic, J. Zhao, and V. Cevher, Robust maximization of non-submodular objectives, in Proc. 21st Int. Conf. Artificial Intelligence and Statistics, Playa Blanca, Spain, 2018, pp. 890–899.
[32]
A. Kuhnle, J. D. Smith, V. G. Crawford, and M. T. Thai, Fast maximization of non-submodular, monotonic functions on the integer lattice, in Proc. 35th Int. Conf. Machine Learning, Stockholm, Sweden, 2018, pp. 2786–2795.
[33]
U. Feige and R. Izsak, Welfare maximization and the supermodular degree, in Proc. 4th Conf. Innovations in Theoretical Computer Science, Berkeley, CA, USA, 2013, pp. 247–256.
[34]
T. Horel and Y. Singer, Maximization of approximately submodular functions, in Proc. 30th Int. Conf. Neural Information Processing Systems, Barcelona, Spain, 2016, pp. 3053–3061.
[35]
Y. J. Jiang, Y. S. Wang, D. C. Xu, R. Q. Yang, and Y. Zhang, Streaming algorithm for maximizing a monotone non-submodular function under d-knapsack constraint, Optim. Lett., vol. 14, no. 5, pp. 1235–1248, 2020.
[36]
T. Soma and Y. Yoshida, Maximizing monotone submodular functions over the integer lattice, Math. Program., vol. 172, no. 1, pp. 539–563, 2018.
[37]
Y. J. Wang, D. C. Xu, Y. S. Wang, and D. M. Zhang, Non-submodular maximization on massive data streams, J. Glob. Optim., vol. 76, no. 4, pp. 729–743, 2020.
[38]
Z. Zhang, D. Du, Y. Jiang, and C. Wu, Maximizing DR-submodular + supermodular functions on the integer lattice subject to a cardinality constraint, J. Glob. Optim., vol. 80, no. 3, pp. 595–616, 2021.
Open Access
Issue
Published:
19 May 2023
)
Download citation
FEEDBACK 
TOP