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
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Blood Leukocyte Object Detection According to Model Parameter-Transfer and Deformable Convolution Kapitel lesen Erstes Kapitel lesen

2021 | OriginalPaper | Buchkapitel

A Streaming Model for Monotone Lattice Submodular Maximization with a Cardinality Constraint

verfasst von : Zhenning Zhang, Longkun Guo, Linyang Wang, Juan Zou

Erschienen in: Parallel and Distributed Computing, Applications and Technologies

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

In this paper, we consider a streaming model of maximizing monotone lattice submodular function with a cardinality constraint on the integer lattice. As (lattice) submodularity does not imply the diminishing return property on the integer lattice, we introduce the Sieve-Streaming algorithm combining with a modified binary search subroutine to solve the problem. We also show it is with an approximation ratio \(1/2-\epsilon \), a memory complexity \(O( \epsilon ^{-1} k\log k)\), and a query complexity \(O( \epsilon ^{-2}\log ^2 k )\) per element.

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 Submodular Maximization with Bounded Marginal Values
Nächstes Kapitel The Prize-Collecting k-Steiner Tree Problem
Literatur
1.
Badanidiyuru, A., Mirzasoleiman, B., Karbasi, A., Krause, A.: Streaming submodular maximization: massive data summarization on the fly. In: Proceedings of SIGKDD, pp. 671–680 (2014)
2.
Gottschalk, C., Peis, B.: Submodular function maximization on the bounded integer lattice. In: Proceedings WAOA, pp. 133–144 (2015)
3.
Huang, C., Kakimura, N.: Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. In: Proceedings of WADS, pp. 438–451 (2019)
4.
E. Kazemi, E., Mitrovic, M., Zadimoghaddam, M., Lattanzi, S., Karbasi, A.: Submodular streaming in all its glory: tight approximation, minimum memory and low adaptive complexity. In: Proceedings of ICML, pp. 3311–3320 (2019)
5.
Kuhnle, A., Smith, J.D., Crawford, V.G., Thai, M.T.: Fast maximization of non-submodular, monotonic functions on the integer lattice. In: Proceedings of ICML, pp. 2791–2800 (2018)
6.
Nong, Q., Fang, J., Gong, S., Du, D., Feng, Y., Qu, X.: A \(1/2\)-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice. J. Comb. Optim. 39, 1208–1220 (2020)MathSciNetCrossRef
7.
Norouzi-Fard, A., Tarnawski, J., Mitrovic, S., Zandieh, A., Mousavifar, A., Svensson, O.: Beyond 1/2-approximation for submodular maximization on massive data streams. In: Proceedings of ICML, pp. 3829–3838 (2018)
8.
Soma, T., Kakimura, N., Inaba, K., Kawarabayashi, K.: Optimal budget allocation: theoretical guarantee and efficient algorithm. In: Proceedings of ICML, pp. 351–359 (2014)
9.
Soma, T., Yoshida, Y.: A generalization of submodular cover via the diminishing return property on the integer lattice. In: Proceedings of NIPS, pp. 847–855 (2015)
10.
Soma, T., Yoshida, Y.: Maximizing monotone submodular functions over the integer lattice. Math. Program. 172, 539–563 (2018)MathSciNetCrossRef
11.
Metadaten
Titel
A Streaming Model for Monotone Lattice Submodular Maximization with a Cardinality Constraint
verfasst von
Zhenning Zhang
Longkun Guo
Linyang Wang
Juan Zou
Copyright-Jahr
2021
Buch
Parallel and Distributed Computing, Applications and Technologies

Print ISBN: 978-3-030-69243-8

Electronic ISBN: 978-3-030-69244-5

Copyright-Jahr: 2021

DOI
https://doi.org/10.1007/978-3-030-69244-5_32