Skip to main content
Erschienen in: Journal of Combinatorial Optimization 4/2020

19.08.2020

A short proof for stronger version of DS decomposition in set function optimization

verfasst von: Xiang Li, H. George Du

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2020

Einloggen

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

search-config
loading …

Abstract

Using a short proof, we show that every set function f can be decomposed into the difference of two monotone increasing and strictly submodular functions g and h, i.e., \(f=g-h\), and every set function f can also be decomposed into the difference of two monotone increasing and strictly supermodular functions g and h, i.e., \(f=g-h\).

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!

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!

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!

Literatur
Zurück zum Zitat Du DZ, Ko KI, Hu X (2012) Design and analysis of approximation algorithms. Springer, BerlinCrossRef Du DZ, Ko KI, Hu X (2012) Design and analysis of approximation algorithms. Springer, BerlinCrossRef
Zurück zum Zitat Gu S, Shi G, Wu W, Lu C (2020) A fast double greedy algorithm for non-monotone DR-submodular function maximization. Discrete Math Algorithm Appl. 12(1):2050007:1–2050007:11MathSciNetCrossRef Gu S, Shi G, Wu W, Lu C (2020) A fast double greedy algorithm for non-monotone DR-submodular function maximization. Discrete Math Algorithm Appl. 12(1):2050007:1–2050007:11MathSciNetCrossRef
Zurück zum Zitat Guo J, Weili W (2019) A novel scene of viral marketing for complementary products. IEEE Trans Comput Soc Syst 6(4):797–808CrossRef Guo J, Weili W (2019) A novel scene of viral marketing for complementary products. IEEE Trans Comput Soc Syst 6(4):797–808CrossRef
Zurück zum Zitat Iyer R, Bilmes J (2012) Algorithms for approximate minimization of the difference between submodular functions. In: Proc, UAI Iyer R, Bilmes J (2012) Algorithms for approximate minimization of the difference between submodular functions. In: Proc, UAI
Zurück zum Zitat Lai L, Ni Q, Lu C, Huang C, Wu W (2019) Monotone submodular maximization over the bounded integer lattice with cardinality constraints. Discret Math Algorithm Appl 11(6):1950075:1–1950075:14MathSciNetCrossRef Lai L, Ni Q, Lu C, Huang C, Wu W (2019) Monotone submodular maximization over the bounded integer lattice with cardinality constraints. Discret Math Algorithm Appl 11(6):1950075:1–1950075:14MathSciNetCrossRef
Zurück zum Zitat Li X, Du HG, Pardalos PM (2020) A variation of DS decomposition in set function optimization. J Comb Optim 40(1):36–44MathSciNetCrossRef Li X, Du HG, Pardalos PM (2020) A variation of DS decomposition in set function optimization. J Comb Optim 40(1):36–44MathSciNetCrossRef
Zurück zum Zitat Lu W, Chen W, Lakshmanan LVS (2015) From competition to complementarity: comparative influence diffusion and maximization. In: Proceedings of the VLDB endowment 9(2): 60–71 Lu W, Chen W, Lakshmanan LVS (2015) From competition to complementarity: comparative influence diffusion and maximization. In: Proceedings of the VLDB endowment 9(2): 60–71
Zurück zum Zitat Narasimhan M, Bilmes J (2005) A submodular-supermodular procedure with applications to discriminative structure learning. In: Proc, UAI Narasimhan M, Bilmes J (2005) A submodular-supermodular procedure with applications to discriminative structure learning. In: Proc, UAI
Zurück zum Zitat Shuyang G, Gao C, Yang R, Weili W, Wang H, Dachuan X (2020) A general method of active friending in different diffusion models in social networks. Soc Netw Anal Min 10(1):41CrossRef Shuyang G, Gao C, Yang R, Weili W, Wang H, Dachuan X (2020) A general method of active friending in different diffusion models in social networks. Soc Netw Anal Min 10(1):41CrossRef
Zurück zum Zitat Yang DN, Hung HJ, Lee WC, Chen W (2013) Maximizing acceptance probability for active friending in online social networks. In: KDD, pp. 713–721 Yang DN, Hung HJ, Lee WC, Chen W (2013) Maximizing acceptance probability for active friending in online social networks. In: KDD, pp. 713–721
Zurück zum Zitat Yuan J, Weili W, Yi L, Ding-Zhu D(2017) Active friending in online social networks. In: BDCAT, pp. 139–148 Yuan J, Weili W, Yi L, Ding-Zhu D(2017) Active friending in online social networks. In: BDCAT, pp. 139–148
Zurück zum Zitat Zhang H, Dinh TN, Thai MT (2013) Maximizing the spread of positive influence in online social networks. In: ICDCS, pp 317–326 Zhang H, Dinh TN, Thai MT (2013) Maximizing the spread of positive influence in online social networks. In: ICDCS, pp 317–326
Metadaten
Titel
A short proof for stronger version of DS decomposition in set function optimization
verfasst von
Xiang Li
H. George Du
Publikationsdatum
19.08.2020
Verlag
Springer US
Erschienen in
Journal of Combinatorial Optimization / Ausgabe 4/2020
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-020-00639-4

Weitere Artikel der Ausgabe 4/2020

Journal of Combinatorial Optimization 4/2020 Zur Ausgabe