nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.05.2023

Algorithms for maximizing monotone submodular function minus modular function under noise

verfasst von: Shufang Gong, Bin Liu, Mengxue Geng, Qizhi Fang

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

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.

Nächster Artikel Retraction Note: Smart logistics with IoT-based enterprise management system using global manufacturing

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

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

Bateni MH, Hajiaghayi M, Zadimoghaddam M (2013) Submodular secretary problem and extensions. ACM Trans Algorithms 9(4):1–23MathSciNetCrossRefMATH

Brualdi RA (1969) Comments on bases in dependence structures. Bull Aust Math Soc 1(2):161–167MathSciNetCrossRefMATH

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

Feige U (1998) A threshold of ln n for approximating set cover. J ACM 45(4):634–652MathSciNetCrossRefMATH

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

Papadimitriou CH, Yannakakis M (1991) Optimization, approximation, and complexity classes. J Comput Syst Sci 43(3):425–440MathSciNetCrossRefMATH

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

Titel: Algorithms for maximizing monotone submodular function minus modular function under noise
verfasst von: Shufang Gong
Bin Liu
Mengxue Geng
Qizhi Fang
Publikationsdatum: 01.05.2023
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2023
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-023-01026-5

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 4/2023

League competitions and fairness

Tree-optimized labeled directed graphs

Improved algorithms in directional wireless sensor networks

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

On anti-Kekulé and s-restricted matching preclusion problems

Algorithms for single machine scheduling problem with release dates and submodular penalties

Premium Partner