Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice

Jingjing Tan; Cuiping Ge; Fengmin Wang; Ziyang Li; Jingjing Tan; Cuiping Ge; Fengmin Wang; Ziyang Li

doi:10.3934/math.2026310

AIMS Mathematics

2026, Volume 11, Issue 3: 7555-7572. doi: 10.3934/math.2026310

Previous Article Next Article

Research article

Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice

1.
School of Mathematics and Statistics, Weifang University, Weifang 261061, China
2.
Shandong Key Laboratory of Intelligent Manufacturing Technology for Advanced Power Equipment, Weifang 261061, China
3.
Beijing Jinghang Research Institute of Computing and Communication, Beijing 100074, China
¹ A preliminary version of this paper appeared in the 30th International Computing and Combi natorics Combinatorics Conference (COCOON 2024), 2025, pp. 324–331.

Received: 29 October 2025 Revised: 30 January 2026 Accepted: 10 February 2026 Published: 23 March 2026
MSC : 90C25

The team formation problem is a very important problem in the labor market that has been proved to be NP-hard. This paper proposes an efficient bicriteria streaming algorithm aimed at striking a balance between gain and cost in team formation problems with cardinality constraints on the integer lattice. To address this, we utilized a model optimized for maximizing the difference between a nonnegative normalized monotone submodular function and a nonnegative linear function. We further consider the case where the first function of the object function is weakly submodular. Combining the lattice binary search with the threshold method, we present an online algorithm called bicriteria streaming algorithmsalgorithm. Concomitantly, we comprehensively analyze both models.
- knapsack constraint,
- integer lattice,
- cardinality function,
- streaming algorithm
Citation: Jingjing Tan, Cuiping Ge, Fengmin Wang, Ziyang Li. Streaming algorithm for balance gain and cost with cardinality constraint on the integer lattice[J]. AIMS Mathematics, 2026, 11(3): 7555-7572. doi: 10.3934/math.2026310

Related Papers:

Abstract

The team formation problem is a very important problem in the labor market that has been proved to be NP-hard. This paper proposes an efficient bicriteria streaming algorithm aimed at striking a balance between gain and cost in team formation problems with cardinality constraints on the integer lattice. To address this, we utilized a model optimized for maximizing the difference between a nonnegative normalized monotone submodular function and a nonnegative linear function. We further consider the case where the first function of the object function is weakly submodular. Combining the lattice binary search with the threshold method, we present an online algorithm called bicriteria streaming algorithmsalgorithm. Concomitantly, we comprehensively analyze both models.

References

[1]	Anagnostopoulos, L. Becchetti, C. Castillo, A. Gionis, S. Leonardi, Online team formation in social networks, in Proceedings of the 21st International Conference on World Wide Web, (2012), 839–848. https://doi.org/10.1145/2187836.2187950
[2]	A. Anagnostopoulos, C. Castillo, A. Fazzone, S. Leonardi, E. Terzi, 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, (2018), 1109–1118. https://doi.org/10.1145/3219819.3220056
[3]	T. Lappas, K. Liu, E. Terzi, Finding a team of experts in social networks, in Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2009), 467–476. https://doi.org/10.1145/1557019.1557074
[4]	Y. Benoist, P. Foulon, F. Labourie, Flots d'Anosov a distributions stable et instable differentiables (French) [Anosov flows with stable and unstable differentiable distributions], J. Amer. Math. Soc., 5 (1992), 33–74. https://doi.org/10.1090/S0894-0347-1992-1124979-1 doi: 10.1090/S0894-0347-1992-1124979-1
[5]	S. Nikolakaki, A. Ene, E. Terzi, An Efficient Framework for Balancing Submodularity and Cost, arXiv preprint arXiv: 2002.07782, (2020). https://doi.org/10.1145/3447548.3467367
[6]	M. Sviridenko, J. Vondrák, J. Ward, Optimal approximation for submodular and supermodular optimization with bounded curvature, Math. Oper. Res., 42 (2017), 1197–1218. https://doi.org/10.1287/moor.2016.0842 doi: 10.1287/moor.2016.0842
[7]	D. Du, Y. Li, N. Xiu, D. Xu, Simultaneous approximation of multi-criteria submodular functions maximization, J. Oper. Res. Soc. China, 2 (2014), 271–290. https://doi.org/10.1007/s40305-014-0053-z doi: 10.1007/s40305-014-0053-z
[8]	M. Feldman, Guess free maximization of submodular and linear sums, in Proceedings of the 16th International Conference Workshop on Algorithms and Data Structures, (2019), 380–394. https://doi.org/10.1007/978-3-030-24766-9_28
[9]	L. Lovasz, On the Shannon capacity of a graph, IEEE T. Inf. Theory, 25 (1979), 1–7. https://doi.org/10.1109/TIT.1979.1055985 doi: 10.1109/TIT.1979.1055985
[10]	T. Soma, Y. Yoshida, Maximization monotone submodular functions over the integer lattice, Math. Program., 172 (2018), 539–563. https://doi.org/10.1007/s10107-018-1324-y doi: 10.1007/s10107-018-1324-y
[11]	C. Gottschalk, B. Peis, Submodular function maximization on the bounded integer lattice, in Proceedings of WAOA, (2015), 133–144. https://doi.org/10.1007/978-3-319-28684-6_12
[12]	Q. Nong, J. Fang, S. Gong, D. Du, Y. Feng, X. Qu, A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice, J. Comb. Optim., 39 (2020), 1208–1220. https://doi.org/10.1007/s10878-020-00558-4 doi: 10.1007/s10878-020-00558-4
[13]	T. Soma, N. Kakimura, K. Inaba, K. Kawarabayashi, Optimal budget allocation: Theoretical guarantee and efficient algorithm, in Proceedings of ICML, (2014), 351–359.
[14]	J. Tan, Y. Xu, D. Zhang, X. Zhang, On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice, J. Comb. Optim., 45 (2023), 1–19. https://doi.org/10.1007/s10878-023-00986-y doi: 10.1007/s10878-023-00986-y
[15]	M. Kapralov, I. Post, J. Vondrák, Online submodular welfare maximization: Greedy is optimal, in Proceedings of SODA, (2012), 1216–1225. https://doi.org/10.1137/1.9781611973105.88
[16]	I. Simon, N. Snavely, S. Seitz, Scene summarization for online image collections, in Proceedings of ICCV, (2007), 1–8. https://doi.org/10.1109/ICCV.2007.4408863
[17]	J. Tan, Y. Xu, D. Zhang, X. Zhang, On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice, J. Comb. Optim., 45 (2023), 1–19. https://doi.org/10.1007/s10878-023-00986-y doi: 10.1007/s10878-023-00986-y
[18]	A. Das, D. Kempe, Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection, in Proceedings of ICML, (2011), 1057–1064.
[19]	A. Bian, J. Buhmann, A. Krause, S. Tschiatschek, Guarantees for greedy maximization of non-submodular functions with applications, in Proceedings of ICML, (2017), 498–507.
[20]	Z. Liu, H. Chang, D. Du, X. Zhang, Improved algorithms for non-submodular function maximization problem, in Proceedings of AAIM, (2021), 190–199. https://doi.org/10.1007/978-3-030-93176-6_17
[21]	A. Kuhnle, J. Smith, V. Crawford, M. Yhai, Fast maximization of nonsubmodular, monotonic functions on the integer lattice, in Proceedings of ICML, (2018), 2791–2800.
[22]	Z. Zhang, B. Liu, Y. Wang, D. Xu, D. Zhang, Greedy algorithm for maximization of non-submodular functions subject to knapsack constraint, in Proceedings of COCOON, (2019), 651–662. https://doi.org/10.1007/978-3-030-26176-4_54
[23]	J. Tan, F. Wang, W. Ye, Q. Zhang, Y. Zhou, Streaming algorithms for monotone non-submodular function maximization under a knapsack constraint on the integer lattice, Theor. Comput. Sci., 937 (2022), 39–49. https://doi.org/10.1016/j.tcs.2022.09.028 doi: 10.1016/j.tcs.2022.09.028

Reader Comments

Your name:*

Email:*
© 2026 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)