Home Tsinghua Science and Technology Article
PDF (730.6 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript
Open Access

Streaming Algorithms for Non-Submodular Maximization on the Integer Lattice

School of Mathematics and Information Science, Weifang University, Weifang 261061, China
Beijing Institute for Scientific and Engineering Computing, Beijing University of Technology, Beijing 100124, China
Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences, Shenzhen 518055, China
School of Mathematical Sciences, Qufu Normal University, Qufu 273165, China
Show Author Information

Abstract

Many practical problems emphasize the importance of not only knowing whether an element is selected but also deciding to what extent it is selected, which imposes a challenge on submodule optimization. In this study, we consider the monotone, nondecreasing, and non-submodular maximization on the integer lattice with a cardinality constraint. We first design a two-pass streaming algorithm by refining the estimation interval of the optimal value. For each element, the algorithm not only decides whether to save the element but also gives the number of reservations. Then, we introduce the binary search as a subroutine to reduce the time complexity. Next, we obtain a one-pass streaming algorithm by dynamically updating the estimation interval of optimal value. Finally, we improve the memory complexity of this algorithm.

Keywords

integer latticenon-submodularstreaming algorithmcardinality constraint

References

[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[18]
U. Feige, A threshold of ln n for approximating set cover, J. ACM, vol. 45, no. 4, pp. 634–652, 1998.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[36]
T. Soma and Y. Yoshida, Maximizing monotone submodular functions over the integer lattice, Math. Program., vol. 172, no. 1, pp. 539–563, 2018.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 28 Issue 5,
October 2023
Pages 888-895
DOI: 10.26599/TST.2022.9010031
Cite this article:
Tan J, Sun Y, Xu Y, et al. Streaming Algorithms for Non-Submodular Maximization on the Integer Lattice. Tsinghua Science and Technology, 2023, 28(5): 888-895. https://doi.org/10.26599/TST.2022.9010031
Metrics & Citations  
Article History
Copyright
Rights and Permissions
Return