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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Streaming Algorithm for Balance Gain and Cost with Knapsack Constraint on the Integer Lattice

  • Jingjing Tan,
  • Meixia Li,
  • Meng Sun,
  • Ruiqi Yang

摘要

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.