Bicriteria streaming algorithms to balance gain and cost with cardinality constraint

Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the differen...

Full description

Saved in:
Bibliographic Details
Published in:Journal of combinatorial optimization 2022-11, Vol.44 (4), p.2946-2962
Main Authors: Wang, Yijing, Xu, Dachuan, Du, Donglei, Jiang, Yanjun
Format: Article
Language:English
Subjects:
Algorithms
Combinatorics
Constraint modelling
Convex and Discrete Geometry
Linear functions
Mathematical Modeling and Industrial Mathematics
Mathematics
Mathematics and Statistics
Operations Research/Decision Theory
Optimization
Theory of Computation
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Team formation plays an essential role in the labor market. In this paper, we propose two bicriteria algorithms to construct a balance between gain and cost in a team formation problem under the streaming model, subject to a cardinality constraint. We formulate the problem as maximizing the difference of a non-negative normalized monotone submodular function and a non-negative linear function. As an extension, we also consider the case where the first function is γ -weakly submodular. Combining the greedy technique with the threshold method, we present bicriteria streaming algorithms and give detailed analysis for both of these models. Our analysis is competitive with that in Ene’s work.
ISSN:1382-6905
1573-2886
DOI:10.1007/s10878-021-00827-w