Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
In Memoriam: Ker-I Ko (1950–2018) Read chapter Read first chapter

2020 | OriginalPaper | Chapter

A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions

Authors : Qingqin Nong, Suning Gong, Qizhi Fang, Dingzhu Du

Published in: Complexity and Approximation

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Better Upper Bounds for Searching on a Line with Byzantine Robots
next chapter Sequential Location Game on Continuous Directional Star Networks
Literature
1.
Ahmed, S., Atamtürk, A.: Maximizing a class of submodular utility functions. Math. Program. 128(1–2), 149–169 (2011)MathSciNetCrossRef
2.
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)
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)
5.
Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3), 1–20 (2018). Article 32MathSciNetCrossRef
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)
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)MathSciNetCrossRef
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)
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)
10.
11.
Feige, U., Mirrokni, V.-S., Vondrák, J.: Maximizing non-monotone submodular functions. SIAM J. Comput. 40(4), 1133–1153 (2011)MathSciNetCrossRef
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)
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)
14.
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)
16.
Hochbaum, D.S.: An efficient algorithm for image segmentation. Markov random fields and related problems. J. ACM 48(4), 686–701 (2001)MathSciNetCrossRef
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)MathSciNetMATH
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)
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)
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)
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)
Metadata
Title
A Survey on Double Greedy Algorithms for Maximizing Non-monotone Submodular Functions
Authors
Qingqin Nong
Suning Gong
Qizhi Fang
Dingzhu Du
Copyright Year
2020
Book
Complexity and Approximation

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

Electronic ISBN: 978-3-030-41672-0

Copyright Year: 2020

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

Premium Partner

    Image Credits