A Bicriteria Streaming Algorithm to Balance Coverage and Cost with Cardinality Constraint

摘要

In this work, we investigate a streaming algorithm with the aim to balance the coverage and cost in team formation. This problem can be formulated as maximizing the difference of two set functions f-ℓ subject to a cardinality constraint, where function f is non-negative monotone approximately submodular, and function ℓ is non-negative linear. We provide a bicriteria algorithm by exploiting the embeded structure.