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.