Top

Journal of Combinatorial Optimization

Published in:

19-03-2020

A variation of DS decomposition in set function optimization

Authors: Xiang Li, H. George Du, Panos M. Pardalos

Published in: Journal of Combinatorial Optimization | Issue 1/2020

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

search-config

AI-assisted search

Off

Abstract

Any set function can be decomposed into the difference of two monotone nondecreasing submodular functions. This theorem plays an important role in the set function optimization theory. In this paper, we show a variation that any set function can be decomposed into the difference of two monotone nondecreasing supermodular functions. Meanwhile, we give an example in social network optimization and construct algorithmic solutions for the maximization problem of set functions with this variation of DS decomposition.

previous article Approximating the asymmetric p-center problem in parameterized complete digraphs

next article Planar graphs without 4- and 6-cycles are (7 : 2)-colorable

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 "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

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

Chen W, Lin T, Tan Z, Zhao M, Zhou X (2016) Robus influence maximization. In: KDD’16. CA, USA, San Francisco

Du DZ, Ko KI, Hu X (2012) Desin and analysis of approximation algorithms. Springer, BerlinCrossRef

Grötschel M, Lovász L, Schrijver A (1988) Geometric algorithms and combinatorial optimization, 2nd edn. Springer, BerlinCrossRef

Gu S, Du H, Thai MT, Du D-Z (2019) Friending. In: Du D-Z, Pardalas PM, Zhang Z (eds) Nonlinear combinatorial optimization. Springer, Berlin, pp 265–272CrossRef

Iyer R, Bilmes J (2012) Algorithms for approximate minimization of the difference between submodular functions. In: Proceeding of UAI

Kempe D, Kleinberg JM, Tardos E (2003) Maximizing the spread of influence through a social network. KDD, pp 137–146

Lu W, Chen W, Lakshmanan LV S (2016a) From competition to complementarity: comparative influence diffusion and maximization. In: Proceeding the VLDB Endowsment, vol 9, no 2, pp 60–71

Lu Z, Zhang Z, Wu W (2016b) Solution of Bharathi–Kempe–Salek conjecture on influence maximization in arborescence. J Comb Optim 33:803–808CrossRef

Narasimhan M, Bilmes J (2005) A submodular–supermodular procedure with applications to discriminative structure learning. In: Proceeding of UAI

Orlin JB (2009) A faster strongly polynomial time algorithm for submodular function minimization. Math Program 118:237C251MathSciNetCrossRef

Schrijver A (2000) A combinatorial algorithm minimizing submodular functions in strong polynomial time. J Comb Theory (B) 80:346–355CrossRef

Schrijver A, Yannakakis M (1991) Simple local search problems that hard to solve. SIAM J Comput 20(1):56–87MathSciNetCrossRef

Wang A, Wu W, Cui L (2016) On Bharathi–Kempe–Salek conjecture on influence maximization in arborescence. J Comb Optim 31:1678–1684MathSciNetCrossRef

Wu WL, Zhang Z, Du DZ (2019) Set function optimization. J Oper Res Soc China 7(2):183–193MathSciNetCrossRef

Yang DN, Hung HJ, Lee WC, Chen W (2013) Maximizing acceptance probability for active friending in online social networks. KDD, Wei Chen, pp 713–721

Yuan J, Wu W, Li Y, Du D-Z (2017) Active friending in online social networks. In: BDCAT 2017, pp 139–148

Zhang H, Dinh MT, Thai MT (2013) Maximizing the spread of positive inuencein online social networks. In: ICDCS 2013, pp 317–326

Title: A variation of DS decomposition in set function optimization
Authors: Xiang Li
H. George Du
Panos M. Pardalos
Publication date: 19-03-2020
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2020
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00560-w

Springer Professional

Abstract

Please log in to get access to your license.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1/2020

Plane graphs with are entirely 10-colorable

The strong chromatic index of graphs with edge weight eight

An improved semi-online algorithm for scheduling on a single machine with unexpected breakdown

Planar graphs without 4- and 6-cycles are (7 : 2)-colorable

A -approximation algorithm for coloring rooted subtrees of a degree 3 tree

New restrictions on defective coloring with applications to steinberg-type graphs

Premium Partner