Streaming Algorithms for Maximizing k-Submodular Functions Under a Partition Matroid Constraint

In numerous real-world scenarios, the objective is to choose multiple sets of disjoint elements rather than just one. Thus a [Formula: see text]-submodular function, which is a natural extension of a submodular function, finds applications in a wide array of contexts. This research is driven by a scenario in which data items within a stream are categorized into distinct groups, each subject to a size constraint. Firstly, we present a multi-pass streaming algorithm that needs [Formula: see text] passes through the data stream. This algorithm achieves a [Formula: see text]-approximation for the monotone case and a [Formula: see text]-approximation for the non-monotone case, respectively, for any constant [Formula: see text]. The query complexity is [Formula: see text], and the memory complexity is [Formula: see text]. And then we propose a one-pass streaming algorithm which returns a [Formula: see text]-approximation ratio for the monotone case and a [Formula: see text]-approximation ratio for the non-monotone case. The query complexity is [Formula: see text], and the memory complexity is [Formula: see text].