We study the problem of finding a maximum matching in a graph given by an input stream listing its edges in some arbitrary order, where the quantity to be maximized is given by a monotone submodular function on subsets of edges. This problem, which we call maximum submodular-function matching (MSM), is a natural generalization of maximum weight matching (MWM). We give two incomparable algorithms for this problem with space usage falling in the semi-streaming range-they store only O(n) edges, using O(n log n) working memory-that achieve approximation ratios of 7.75 in a single pass and (3 + ε) in O(ε~(-3)) passes respectively. The operations of these algorithms mimic those of known MWM algorithms. We identify a general framework that allows this kind of adaptation to a broader setting of constrained submodular maximization.
展开▼
