nach oben

Journal of Combinatorial Optimization

Erschienen in:

02.11.2021

Bicriteria streaming algorithms to balance gain and cost with cardinality constraint

verfasst von: Yijing Wang, Dachuan Xu, Donglei Du, Yanjun Jiang

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

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the difference of a non-negative normalized monotone submodular function and a non-negative linear function. As an extension, we also consider the case where the first function is \(\gamma \)-weakly submodular. Combining the greedy technique with the threshold method, we present bicriteria streaming algorithms and give detailed analysis for both of these models. Our analysis is competitive with that in Ene’s work.

Vorheriger Artikel Measuring the influence and amplification of users on social network with unsupervised behaviors learning and efficient interaction-based knowledge graph

Nächster Artikel On zero-error codes produced by greedy algorithms

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

Anagnostopoulos A, Becchetti L, Castillo C, Gionis A, Leonardi S (2012) Online team formation in social networks. In: Proceedings of the 21st international conference on world wide web, pp 839–848

Anagnostopoulos A, Castillo C, Fazzone A, Leonardi S, Terzi E (2018) Algorithms for hiring and outsourcing in the online labor market. In: Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery and data mining, pp 1109–1118

Badanidiyuru A, Mirzasoleiman B, Karbasi A, Krause A (2014) Streaming submodular maximization: massive data summarization on the fly. In: Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining, pp 671–680

Bertsimas D, Van Parys B (2020) Sparse high-dimensional regression: exact scalable algorithms and phase transitions. Ann Stat 48:300–323MathSciNetCrossRef

Bian AA, Buhmann JM, Krause A, Tschiatschek S (2017) Guarantees for greedy maximization of non-submodular functions with applications. In: Proceedings of the 34th international conference on machine learning, pp 498–507

Du D, Li Y, Xiu N, Xu D (2014) Simultaneous approximation of multi-criteria submodular functions maximization. J Oper Res Soc China 2:271–290MathSciNetCrossRef

Ene A (2020) A note on maximizing the difference between a monotone submodular function and a linear function. ArXiv preprint arXiv: 2002.07782

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

Feldman M (2019) Guess free maximization of submodular and linear sums. In: Proceedings of the 16th international conference workshop on algorithms and data structures, pp 380–394

Friedrich T, Göbel A, Neumann F, Quinzan F, Rothenberger R (2019) Greedy maximization of functions with bounded curvature under partition matroid constraints. In: Proceedings of the 33rd AAAI conference on artificial intelligence, pp 2272–2279

Gargano L, Hell P, Peters JG, Vaccaro U (2015) Influence diffusion in social networks under time window constraints. Theoret Comput Sci 584:53–66MathSciNetCrossRef

Golshan B, Lappas T, Terzi E (2014) Profit-maximizing cluster hires. In: Proceedings of the 20th ACM SIGKDD international conference on knowledge discovery and data mining, pp 1196–1205

Gong S, Nong Q, Liu W, Fang Q (2019) Parametric monotone function maximization with matroid constraints. J Global Optim 75:833–849MathSciNetCrossRef

Harshaw C, Feldman M, Ward J, Karbasi A (2019) Submodular maximization beyond non-negativity: guarantees, fast algorithms, and applications. In: Proceedings of the 36th international conference on machine learning, pp 2634–2643

Hu H, Grubb A, Bagnell JA, Hebert M (2016) Efficient feature group sequencing for anytime linear prediction. In: Proceedings of the 32nd conference on uncertainty in artificial intelligence, pp 279–288

Kuhnle A, Smith JD, Crawford VG, Thai MT (2018) Fast maximization of non-submodular, monotonic functions on the integer lattice. In: Proceedings of the 35th international conference on machine learning, pp 2791–2800

Lappas T, Liu K, Terzi E (2009) Finding a team of experts in social networks. In: Proceedings of the 15th ACM SIGKDD international conference on knowledge discovery and data mining, pp 467–476

Liu S, Poon CK (2017) A simple greedy algorithm for the profit-aware social team formation problem. In: Proceedings of the 11th international conference on combinatorial optimization and applications, pp 379–393

Muthukrishnan S (2005) Data streams: algorithms and applications. Found Trends Theor Comput Sci 1:117–236MathSciNetCrossRef

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

Qian C (2019) Multi-objective evolutionary algorithms are still good: maximizing monotone approximately submodular minus modular functions. ArXiv preprint arXiv: 1910.05492

Sviridenko M, Vondrák J, Ward J (2017) Optimal approximation for submodular and supermodular optimization with bounded curvature. Math Oper Res 42:1197–1218MathSciNetCrossRef

Wang Y, Xu D, Wang Y, Zhang D (2020) Non-submodular maximization on massive data streams. J Global Optim 76:729–743MathSciNetCrossRef

Wu M, Wicker M, Ruan W, Huang X, Kwiatkowska M (2020) A game-based approximate verification of deep neural networks with provable guarantees. Theoret Comput Sci 807:298–329MathSciNetCrossRef

Yu Q, Li H, Liao Y, Cui S (2018) Fast budgeted influence maximization over multi-action event logs. IEEE Access 6:14367–14378CrossRef

Titel: Bicriteria streaming algorithms to balance gain and cost with cardinality constraint
verfasst von: Yijing Wang
Dachuan Xu
Donglei Du
Yanjun Jiang
Publikationsdatum: 02.11.2021
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2022
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-021-00827-w

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/2022

A data structure for efficiently managing a set of energy functions

Constructing tree decompositions of graphs with bounded gonality

Surface polygonization of 3D objects using norm similarity

Approximation algorithms with constant ratio for general cluster routing problems

Principal–agent problem under the linear contract

An integrated method for hybrid distribution with estimation of demand matching degree

Premium Partner