Streaming Algorithm for Balance Gain and Cost with Knapsack Constraint on the Integer Lattice
摘要
The selection strategy of team members in social networks is the key to team formation, which has been proved to be NP-hard problem. This paper proposes a streaming algorithm aimed to striking a balance between gain and cost in team formation problems with knapsack constraints on the integer lattice. In this paper, we transform the problem into an optimization model, that is, to maximize the difference between a monotone DR-submodule function and a non-negative linear function. With the help of lattice binary search and threshold method, we design an online bi-criteria streaming algorithms.