Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching, Matroid, and Matchoid Constraints
share
We consider the problem of maximizing a non-negative submodular function under the b-matching constraint, in the semi-streaming model. When the function is linear, monotone, and non-monotone, we obtain the approximation ratios of 2+ε, 3 + 2 √(2)≈ 5.828, and 4 + 2 √(3)≈ 7.464, respectively. We also consider a generalized problem, where a k-uniform hypergraph is given, along with an extra matroid or a k'-matchoid constraint imposed on the edges, with the same goal of finding a b-matching that maximizes a submodular function. When the extra constraint is a matroid, we obtain the approximation ratios of k + 1 + ε, k + 2√(k+1) + 2, and k + 2√(k + 2) + 3 for linear, monotone and non-monotone submodular functions, respectively. When the extra constraint is a k'-matchoid, we attain the approximation ratio 8/3k+ 64/9k' + O(1) for general submodular functions.
READ FULL TEXT