Affiliations:
1School of Mathematics and Statistics, Weifang University, Weifang, Shandong 261061, China
2Shandong Key Laboratory of Intelligent Manufacturing Technology for Advanced Power Equipment, Weifang 261061, China
3School of Mathematics, Statistics and Mechanics, Beijing University of Technology, Beijing 100074, China
4Department of General Education, Jinan Vocational College of Nursing, Jinan, Shandong 250100, China
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.
DR-submodular function, Integer lattice, Team formation, Streaming algorithm, Knapsack constraint
https://doi.org/10.21833/ijaas.2026.03.011
Tan, J., Li, M., Sun, M., Yang, R., & 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. https://doi.org/10.21833/ijaas.2026.03.011