Guaranteed Nonconvex Optimization Submodular Maximization Over Continuous Domains

Abstract

Maximizing non-monotone submodular functions is one of the most important problems in submodular optimization. A breakthrough work on the problem is the double-greedy technique introduced by Buchbinder et al. [7]. Prior work has shown that this technique is very effective. This paper surveys on double-greedy algorithms for maximizing non-monotone submodular functions from discrete domains of sets and integer lattices to continuous domains.

Keywords

• Submodular
• Non-monotone
• Algorithm
• Double greedy

This research was supported in part by the National Natural Science Foundation of China under grant numbers 11201439 and 11871442, and was also supported in part by the Natural Science Foundation of Shandong Province under grant number ZR2019MA052 and the Fundamental Research Funds for the Central Universities.

References

1. Ahmed, S., Atamtürk, A.: Maximizing a class of submodular utility functions. Math. Program. 128(1–2), 149–169 (2011)

   CrossRef  MathSciNet  Google Scholar

2. Bach, F.: Submodular functions: from discrete to continuous domains. Math. Program. 175(1–2), 419–459 (2019)

   CrossRef  MathSciNet  Google Scholar

3. Balcan, M.-F., Harvey, N.-J.-A.: Learning submodular functions. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, pp. 793–802. ACM. San Jose, CA, USA (2011)

   Google Scholar

4. Bian, A., Mirzasoleiman, B., Buhmann, J., Krause, A.: Guaranteed nonconvex optimization: submodular maximization over continuous domains. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 111–120. JMLR. Fort Lauderdale, Florida, USA (2017)

   Google Scholar

5. Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3), 1–20 (2018). Article 32

   CrossRef  MathSciNet  Google Scholar

6. Buchbinder, N., Feldman, M., Naor, J.-S., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, Oregon, Portland, pp. 1433–1452 (2014)

   Google Scholar

7. Buchbinder, N., Feldman, M., Seffi, J., Schwartz, R.: A tight linear time (1/2)-approximation for unconstrained submodular maximization. SIAM J. Comput. 44(5), 1384–1402 (2015)

   CrossRef  MathSciNet  Google Scholar

8. Chen, L., Feldman, M., Karbasi, A.: Unconstrained submodular maximization with constant adaptive complexity. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC, Phoenix, AZ, USA, pp. 102–113 (2019)

   Google Scholar

9. Ene, A., Nguy\(\tilde{\hat{\text{e}}}\)n, H.-L.: Constrained submodular maximization: beyond \(1/e\). In: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS, New Brunswick, NJ, USA, pp. 248–258 (2016)

   Google Scholar

10. Ene, A., Nguy\(\tilde{\hat{\text{ e }}}\)n, H.-L., Vladu, A.: A parallel double greedy algorithm for submodular maximization (2018). https://arxiv.org/abs/1812.01591

11. Feige, U., Mirrokni, V.-S., Vondrák, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133–1153 (2011)

    CrossRef  MathSciNet  Google Scholar

12. 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, FOCS, pp. 570–579. Palm Springs, CA, USA (2011)

    Google Scholar

13. Gharan, S.-O., Vondrák J.: Submodular maximization by simulated annealing. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1098–1117. Society for Industrial and Applied Mathematics, San Francisco, California, USA (2011)

    Google Scholar

14. Gottschalk, C., Peis, B.: Submodular function maximization on the bounded integer lattice. In: Sanità, L., Skutella, M. (eds.) WAOA 2015. LNCS, vol. 9499, pp. 133–144. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28684-6_12

    CrossRef  Google Scholar

15. Hartline, J., Mirrokni, V., Sundararajan, M.: Optimal marketing strategies over social networks. In: Proceedings of the 17th International Conference on World Wide Web, pp. 189–198. ACM. Beijing, China (2008)

    Google Scholar

16. Hochbaum, D.S.: An efficient algorithm for image segmentation. Markov random fields and related problems. J. ACM 48(4), 686–701 (2001)

    CrossRef  MathSciNet  Google Scholar

17. Hochbaum, D.S., Hong, S.P.: About strongly polynomial time algorithms for quadratic optimization over submodular constraints. Math. Program. 69(1), 269–309 (1995)

    MathSciNet  MATH  Google Scholar

18. Kapralov, M., Post, I., Vondrák, J.: Online submodular welfare maximization: greedy is optimal. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1216–1225. SIAM, New Orleans, Louisiana, USA (2013)

    Google Scholar

19. Niazadeh, R., Roughgarden, T.: Optimal algorithms for continuous non-monotone submodular and DR-submodular maximization. In: the 32nd Conference on Neural Information Processing Systems, NIPS, Montréal, Canada, pp. 9617–9627 (2018)

    Google Scholar

20. Soma, T., Yoshida, Y.: A generalization of submodular cover via the diminishing return property on the integer lattice. In: Advances in Neural Information Processing Systems, pp. 847–855 (2015)

    Google Scholar

21. Soma, T., Yoshida, Y.: Non-monotone DR-submodular function maximization. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence, pp. 898–904. AAAI, San Francisco, California, USA (2017)

    Google Scholar

Download references

Author information

Authors and Affiliations

1. School of Mathematical Science, Ocean University of China, Qingdao, 266100, Shandong, People's Republic of China

   Qingqin Nong, Suning Gong & Qizhi Fang

2. Department of Computer Science, University of Texas, Dallas, 75083, USA

   Dingzhu Du

Corresponding author

Correspondence to Suning Gong .

Editor information

Editors and Affiliations

1. The University of Texas at Dallas, Richardson, TX, USA

   Ding-Zhu Du

2. University of Massachusetts Lowell, Lowell, MA, USA

   Jie Wang

Copyright information

© 2020 Springer Nature Switzerland AG

About this chapter

Cite this chapter

Nong, Q., Gong, S., Fang, Q., Du, D. (2020). A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions. In: Du, DZ., Wang, J. (eds) Complexity and Approximation. Lecture Notes in Computer Science(), vol 12000. Springer, Cham. https://doi.org/10.1007/978-3-030-41672-0_10

Download citation

• .RIS
• .ENW
• .BIB

• DOI : https://doi.org/10.1007/978-3-030-41672-0_10

• Published: 21 February 2020

• Publisher Name: Springer, Cham

• Print ISBN: 978-3-030-41671-3

• Online ISBN: 978-3-030-41672-0

• eBook Packages: Computer Science Computer Science (R0)

leedound1942.blogspot.com

Source: https://link.springer.com/chapter/10.1007/978-3-030-41672-0_10

Share this post