Volume 13, Issue 3 (March 2026), Pages: 105-114

----------------------------------------------

 Original Research Paper

Streaming algorithm for the team formation problem on an integer lattice

 Author(s): 

Jingjing Tan ^{1, 2,} *, Meixia Li ³, Meng Sun ¹, Ruiqi Yang ³, Xiaoqing Zhang ⁴

 Affiliation(s):

¹School of Mathematics and Statistics, Weifang University, Weifang, Shandong 261061, China
²Shandong Key Laboratory of Intelligent Manufacturing Technology for Advanced Power Equipment, Weifang 261061, China
³School of Mathematics, Statistics and Mechanics, Beijing University of Technology, Beijing 100074, China
⁴Department of General Education, Jinan Vocational College of Nursing, Jinan, Shandong 250100, China

 Full text

    Full Text - PDF

 * Corresponding Author. 

   Corresponding author's ORCID profile:  https://orcid.org/0000-0002-9941-0629

 Digital Object Identifier (DOI)

  https://doi.org/10.21833/ijaas.2026.03.011

 Abstract

In social networks, selecting appropriate team members is a key challenge in team formation. This problem has been proven to be NP-hard, meaning that obtaining an optimal solution within polynomial time is generally infeasible. In this study, the team formation problem is formulated as an optimization model that aims to maximize the difference between a monotone DR-submodular function and a non-negative linear function. To address this optimization problem, we propose an online bicriteria streaming algorithm that combines lattice-based binary search with thresholding techniques. Because determining the optimal threshold values in advance is difficult, we introduce Algorithm 3, which dynamically constructs estimation intervals for thresholds and iteratively approaches near-optimal decision boundaries. In addition, we examine a more general case in which the first function is relaxed from a DR-submodular function to a non-submodular function. For this scenario, a corresponding streaming algorithm is also developed. Finally, theoretical analyses of space complexity and time complexity are presented, demonstrating the scalability and computational efficiency of the proposed algorithms for large-scale data environments.

 © 2026 The Authors. Published by IASE.

 This is an open access article under the CC BY-NC-ND license (https://creativecommons.org/licenses/by-nc-nd/4.0/).

 Keywords

DR-submodular function, Integer lattice, Team formation, Streaming algorithm, Knapsack constraint

 Article history

Received 12 September 2025, Received in revised form 5 March 2026, Accepted 9 March 2026

 Acknowledgment

The first author is supported by the Natural Science Foundation of China (No.12301417) and the National Natural Science Foundation of Shandong Province (No. ZR2022MA034). The second author is supported by the Natural Science Foundation of China (Nos.11401438, 11571120). The fourth author is supported by the National Natural Science Foundation of China (No.12101587). 

 Compliance with ethical standards

 Citation:

Tan J, Li M, Sun M, Yang R, and Zhang X (2026). Streaming algorithm for the team formation problem on an integer lattice. International Journal of Advanced and Applied Sciences, 13(3): 105-114

  Permanent Link to this page

 Figures

  Fig. 1 Fig. 2

 Tables

  No Table

---------------------------------------------- 

 References (18)

1. Anagnostopoulos A, Becchetti L, Castillo C, Gionis A, and Leonardi S (2012). Online team formation in social networks. In the Proceedings of the 21st International Conference on World Wide Web, ACM, Lyon, France: 839-848. https://doi.org/10.1145/2187836.2187950   [Google Scholar] PMCid:PMC9645621

2. Anagnostopoulos A, Castillo C, Fazzone A, Leonardi S, and Terzi E (2018). Algorithms for hiring and outsourcing in the online labor market. In the Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, ACM, London, UK: 1109-1118. https://doi.org/10.1145/3219819.3220056   [Google Scholar] PMid:30278844

3. Byrnes KM (2015). A tight analysis of the submodular–supermodular procedure. Discrete Applied Mathematics, 186: 275-282. https://doi.org/10.1016/j.dam.2015.01.026   [Google Scholar]

4. Du DL, Li Y, Xiu NH, and Xu DC (2014). Simultaneous approximation of multi-criteria submodular function maximization. Journal of the Operations Research Society of China, 2: 271-290. https://doi.org/10.1007/s40305-014-0053-z   [Google Scholar]

5. Feldman M (2021). Guess free maximization of submodular and linear sums. Algorithmica, 83: 853-878. https://doi.org/10.1007/s00453-020-00757-9   [Google Scholar]

6. Gottschalk C and Peis B (2015). Submodular function maximization on the bounded integer lattice. In: Sanità L and Skutella M (Eds.), International workshop on approximation and online algorithms: 133-144. Springer, Cham, Switzerland. https://doi.org/10.1007/978-3-319-28684-6_12   [Google Scholar]

7. Kapralov M, Post I, and Vondrák J (2013). Online submodular welfare maximization: Greedy is optimal. In the Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, New Orleans, USA: 1216-1225. https://doi.org/10.1137/1.9781611973105.88   [Google Scholar]

8. Lappas T, Liu K, and Terzi E (2009). Finding a team of experts in social networks. In the Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Paris, France: 467-476. https://doi.org/10.1145/1557019.1557074   [Google Scholar] PMCid:PMC9645621

9. Lovász L (1979). On the Shannon capacity of a graph. IEEE Transactions on Information Theory, 25(1): 1-7. https://doi.org/10.1109/TIT.1979.1055985   [Google Scholar]

10. Nikolakaki SM, Ene A, and Terzi E (2021). An efficient framework for balancing submodularity and cost. In the Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, ACM, Singapore, Singapore: 1256-1266. https://doi.org/10.1145/3447548.3467367   [Google Scholar]

11. Nong Q, Fang J, Gong S, Du D, Feng Y, and Qu X (2020). A 1/2-approximation algorithm for maximizing a non-monotone weak-submodular function on a bounded integer lattice. Journal of Combinatorial Optimization, 39(4): 1208-1220. https://doi.org/10.1007/s10878-020-00558-4   [Google Scholar]

12. Sarpatwar KK, Schieber B, and Shachnai H (2019). Constrained submodular maximization via greedy local search. Operations Research Letters, 47(1): 1-6. https://doi.org/10.1016/j.orl.2018.11.002   [Google Scholar]

13. Soma T and Yoshida Y (2018). Maximizing monotone submodular functions over the integer lattice. Mathematical Programming, 172: 539-563. https://doi.org/10.1007/s10107-018-1324-y   [Google Scholar]

14. Sviridenko M, Vondrák J, and Ward J (2017). Optimal approximation for submodular and supermodular optimization with bounded curvature. Mathematics of Operations Research, 42(4): 1197-1218. https://doi.org/10.1287/moor.2016.0842   [Google Scholar]

15. Tan J, Li M, Sun M, and Yang R (2024). Streaming algorithm for balance gain and cost with knapsack constraint on the integer lattice. In: Li Y, Zhang Y, and Xu J (Eds.), Parallel and distributed computing: Applications and technologies: 534-540. Springer, Singapore, Singapore. https://doi.org/10.1007/978-981-96-4207-6_48   [Google Scholar]

16. Tan J, Xu Y, Zhang D, and Zhang X (2023). On streaming algorithms for maximizing a supermodular function plus a MDR-submodular function on the integer lattice. Journal of Combinatorial Optimization, 45: 55. https://doi.org/10.1007/s10878-023-00986-y   [Google Scholar]

17. Wang Y, Xu D, Du D, and Jiang Y (2022). Bicriteria streaming algorithms to balance gain and cost with cardinality constraint. Journal of Combinatorial Optimization, 44: 2946-2962. https://doi.org/10.1007/s10878-021-00827-w   [Google Scholar]

18. Wang Y, Xu Y, and Yang X (2021). On maximizing the difference between an approximately submodular function and a linear function subject to a matroid constraint. In: Du DZ, Du D, Wu C, and Xu D (Eds.), Combinatorial optimization and applications: 75-85. Springer International Publishing, Cham, Switzerland. https://doi.org/10.1007/978-3-030-92681-6_7   [Google Scholar]