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
Journal of Combinatorial Optimization
Published in: Journal of Combinatorial Optimization 4/2023

01-05-2023

Algorithms for maximizing monotone submodular function minus modular function under noise

Authors: Shufang Gong, Bin Liu, Mengxue Geng, Qizhi Fang

Published in: Journal of Combinatorial Optimization | Issue 4/2023

Log in

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

search-config
loading …

Abstract

Submodular function has the property of diminishing marginal gain, and thus it has a wide range of applications in combinatorial optimization and in emerging disciplines such as machine learning and artificial intelligence. For any set S, most of previous works usually do not consider how to compute f(S) , but assume that there exists an oracle that will output f(S) directly. In reality, however, the process of computing the exact f is often inevitably inaccurate or costly. At this point, we adopt the easily available noise version F of f. In this paper, we investigate the problems of maximizing a non-negative monotone normalized submodular function minus a non-negative modular function under the \(\varepsilon \)-multiplicative noise in three situations, i.e., the cardinality constraint, the matroid constraint and the online unconstraint. For the above problems, we design three deterministic bicriteria approximation algorithms using greedy and threshold ideas and furthermore obtain good approximation guarantees.
next article Retraction Note: Smart logistics with IoT-based enterprise management system using global manufacturing

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
Literature
Chambers CP, Echenique F (2016) Revealed preference theory. Cambridge University Press, EnglandMATH
Chen Y, Hassani SH, Karbasi A (2015) Sequential information maximization: when is greedy near-optimal? In: Proceedings of The 28th Conference on Learning Theory, pp. 338-363. Paris, France
Das A, Kempe D (2018) Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection. J Mach Learn Res 19(1):74–107MathSciNetMATH
Du DL, Li Y, Xiu NH (2014) Simultaneous approximation of multi-criteria submodular function maximization. J Oper Res Soc China 2(3):271–290MathSciNetCrossRefMATH
Edmonds J (2003) Submodular functions, matroids, and certain polyhedra. In: Jünger M, Reinelt G, Rinaldi G (eds) Combinatorial optimization ? Eureka, You Shrink!. Lecture notes in computer science, vol. 2570, pp. 11–26. Springer, Berlin, Heidelberg
Feldman V (2009) On the power of membership queries in agnostic learning. J Mach Learn Res 10:163–182MathSciNetMATH
Gölz P, Procaccia AD (2019) Migration as submodular optimization. In: Proceedings of the 33rd AAAI conference on artificial intelligence, pp. 549-556. Honolulu, Hawaii, USA
Grötschel M, Lovász L, Schrijver A (2012) Geometric algorithms and combinatorial optimization. Springer-Verlag, Berlin, GermanyMATH
Harshaw C, Feldman M, Ward J (2019) Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In: Proceedings of the 36th international conference on machine learning, pp. 2634–2643. Long Beach, California, USA
Horel T, Singer Y (2016) Maximization of approximately submodular functions. In: Proceedings of the 30th international conference on neural information processing systems, pp. 3045-3053. Barcelona, Spain
Iwata S, Fleischer L, Fujishige S (2001) A combinatorial strongly polynomial algorithm for minimizing submodular functions. J ACM 48(4):761–777MathSciNetCrossRefMATH
Iwata S, Nagano K (2009) Submodular function minimization under covering constraints. In: Proceedings of the 50th annual IEEE symposium on foundations of computer science, pp. 671–680. Atlanta, Georgia, USA
Koufogiannakis C, Young NE (2013) Greedy \(\Delta \)-approximation algorithm for covering with arbitrary constraints and submodular cost. Algorithmica 66(1):113–152MathSciNetCrossRefMATH
Krause A, Leskovec J, Isovitsch S (2006) Optimizing sensor placements in water distribution systems using submodular function maximization. In: Proceedings of the 8th international conference on water distribution systems analysis symposium. pp. 1–17. Cincinnati, Ohio
Liu MY, Tuzel O, Ramalingam S (2013) Entropy-rate clustering: cluster analysis via maximizing a submodular function subject to a matroid constraint. IEEE Trans Pattern Anal Mach Intell 36(1):99–112CrossRef
Nikolakaki SM, Ene A, Terzi E (2021) An efficient framework for balancing submodularity and cost. In: Proceedings of the 27th ACM SIGKDD conference on knowledge discovery and data mining, pp. 1256–1266. Virtual Event/Singapore
Qian C (2021) Multiobjective evolutionary algorithms are still good: maximizing monotone approximately submodular minus modular functions. Evol Comput 29(4):463–490CrossRef
Singla A, Tschiatschek S, Krause A (2016) Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. In: Proceedings of the 30th AAAI conference on artificial intelligence. pp. 12-17. Phoenix, Arizona, USA
Sviridenko M, Vondrak J, Ward J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math Oper Res 42(4):1197–1218MathSciNetCrossRefMATH
Svitkina Z, Fleischer L (2011) Submodular approximation: sampling-based algorithms and lower bounds. SIAM J Comput 40(6):1715–1737MathSciNetCrossRefMATH
Wang Y, Xu Y, Yang X (2021) On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint. In: Proceedings of the 15th international conference on combinatorial optimization and applications, pp. 75–85. Tianjin, China
Xiao D, Guo L, Liao K (2021) Streaming submodular maximization under differential privacy noise. In: Proceedings of the 15th international conference on combinatorial optimization and applications. pp. 431–444. Tianjin, China
Yang R, Xu D, Cheng Y (2019) Streaming submodular maximization under noises. In: Proceedings of the 39th international conference on distributed computing systems, pp. 348–357
Zhang H, Zhang H, Kuhnle A (2016) Profit maximization for multiple products in online social networks. In: Proceedings of the 35th annual IEEE international conference on computer communications, pp. 1–9
Metadata
Title
Algorithms for maximizing monotone submodular function minus modular function under noise
Authors
Shufang Gong
Bin Liu
Mengxue Geng
Qizhi Fang
Publication date
01-05-2023
Publisher
Springer US
Published in
Journal of Combinatorial Optimization / Issue 4/2023
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI
https://doi.org/10.1007/s10878-023-01026-5

Other articles of this Issue 4/2023

Journal of Combinatorial Optimization 4/2023 Go to the issue

OriginalPaper

Due date assignment single-machine scheduling with delivery times, position-dependent weights and deteriorating jobs

OriginalPaper

Precedence-constrained covering problems with multiplicity constraints

OriginalPaper

A combination of TEXTCNN model and Bayesian classifier for microblog sentiment analysis

OriginalPaper

Pilot pattern design scheme with branch and bound in PSA-OFDM system

OriginalPaper

Improved algorithms in directional wireless sensor networks

OriginalPaper

Tree-optimized labeled directed graphs

Premium Partner

    Image Credits