Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Stochastic Non-monotone DR-Submodular Maximization Problem over a Convex Set Kapitel lesen Erstes Kapitel lesen

2022 | OriginalPaper | Buchkapitel

Improved Deterministic Algorithms for Non-monotone Submodular Maximization

verfasst von : Xiaoming Sun, Jialin Zhang, Shuo Zhang, Zhijie Zhang

Erschienen in: Computing and Combinatorics

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Submodular maximization is one of the central topics in combinatorial optimization. It has found numerous applications in the real world. In the past decades, a series of algorithms have been proposed for this problem. However, most of the state-of-the-art algorithms are randomized. There remain non-negligible gaps with respect to approximation ratios between deterministic and randomized algorithms in submodular maximization. In this paper, we propose deterministic algorithms with improved approximation ratios for non-monotone submodular maximization. Specifically, for the matroid constraint, we provide a deterministic \(0.283-o(1)\) approximation algorithm, while the previous best deterministic algorithm only achieves a 1/4 approximation ratio. For the knapsack constraint, we provide a deterministic 1/4 approximation algorithm, while the previous best deterministic algorithm only achieves a 1/6 approximation ratio.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Approximation Schemes for k-Facility Location
Nächstes Kapitel Distributed Dominating Sets in Interval Graphs
Literatur
1.
Amanatidis, G., Fusco, F., Lazos, P., Leonardi, S., Reiffenhäuser, R.: Fast adaptive non-monotone submodular maximization subject to a knapsack constraint. In: 33 Proceedings of the Conference on Advances in Neural Information Processing System: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020. vol. 33, pp. 16903–16915. Curran Associates, Inc. (2020)
2.
Badanidiyuru, A., Vondrák, J.: Fast algorithms for maximizing submodular functions. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 1497–1514. SIAM (2014)
3.
Buchbinder, N., Feldman, M.: Deterministic algorithms for submodular maximization problems. ACM Trans. Algorithms 14(3), 32:1–32:20 (2018)
4.
Buchbinder, N., Feldman, M.: Constrained submodular maximization via a nonsymmetric technique. Math. Oper. Res. 44(3), 988–1005 (2019)MathSciNetCrossRefMATH
5.
Buchbinder, N., Feldman, M., Garg, M.: Deterministic (1/2 + \(\epsilon \))-approximation for submodular maximization over a matroid. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, pp. 241–254. SIAM (2019)
6.
Buchbinder, N., Feldman, M., Naor, J., Schwartz, R.: Submodular maximization with cardinality constraints. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, pp. 1433–1452. SIAM (2014)
7.
Das, A., Kempe, D.: Algorithms for subset selection in linear regression. In: Proceedings of the Fortieth Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 45–54. ACM (2008)
8.
9.
Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, pp. 570–579. IEEE Computer Society (2011)
10.
Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions - II. In: Balinski, M.L., Hoffman, A.J. (eds.) Polyhedral Combinatorics, vol 8. pp. 73–87. Springe, Berlin (1978). https://​doi.​org/​10.​1007/​BFb0121195
11.
Gharan, S.O., Vondrák, J.: Submodular maximization by simulated annealing. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, pp. 1098–1116 (2011)
12.
13.
Han, K., Cao, Z., Cui, S., Wu, B.: Deterministic approximation for submodular maximization over a matroid in nearly linear time. In: 33rd Proceedings of the Conference on Advances in Neural Information Processing Systems: Annual Conference on Neural Information Processing Systems, NeurIPS 2020 (2020)
14.
Iyer, R.K., Bilmes, J.A.: Submodular optimization with submodular cover and submodular knapsack constraints. In: 26th Proceedings of the Conference on Advances in Neural Information Processing Systems: Annual Conference on Neural Information Processing Systems 2013, NeurIPS 2013, pp. 2436–2444 (2013)
15.
Kempe, D., Kleinberg, J., Tardos, E.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2003, pp. 137–146. Association for Computing Machinery (2003)
16.
Khanna, R., Elenberg, E., Dimakis, A., Negahban, S., Ghosh, J.: Scalable Greedy Feature Selection via Weak Submodularity. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics. Proceedings of Machine Learning Research, vol. 54, pp. 1560–1568. PMLR (2017)
17.
18.
Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, pp. 545–554. SIAM (2009)
19.
Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discret. Math. 23, 2053–2078 (2010)MathSciNetCrossRefMATH
20.
Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A.: Fast constrained submodular maximization: personalized data summarization. In: Proceedings of the 33nd International Conference on Machine Learning, ICML 2016. JMLR Workshop and Conference Proceedings, vol. 48, p. 1358–1366. JMLR.org (2016)
21.
Nemhauser, G.L., Wolsey, L.A.: Best algorithms for approximating the maximum of a submodular set function. Math. Oper. Res. 3(3), 177–188 (1978)MathSciNetCrossRefMATH
22.
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions - I. Math. Program. 14(1), 265–294 (1978)MathSciNetCrossRefMATH
23.
Schrijver, A., et al.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Heidelberg (2003)
24.
25.
Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41–43 (2004)MathSciNetCrossRefMATH
26.
Vondrák, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 67–74. ACM (2008)
Metadaten
Titel
Improved Deterministic Algorithms for Non-monotone Submodular Maximization
verfasst von
Xiaoming Sun
Jialin Zhang
Shuo Zhang
Zhijie Zhang
Copyright-Jahr
2022
Buch
Computing and Combinatorics

Print ISBN: 978-3-031-22104-0

Electronic ISBN: 978-3-031-22105-7

Copyright-Jahr: 2022

DOI
https://doi.org/10.1007/978-3-031-22105-7_44

Premium Partner

    Bildnachweise