Authors: Amit Chakrabarti Sagar Kale
Publish Date: 2015/03/31
Volume: 154, Issue: 1-2, Pages: 225-247
Abstract
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 submodularfunction matching MSM is a natural generalization of maximum weight matching MWM which is in turn a generalization of maximum cardinality matching We give two incomparable algorithms for this problem with space usage falling in the semistreaming range—they store only On edges using Onlog n working memory—that achieve approximation ratios of 775 in a single pass and 3+varepsilon in Ovarepsilon 3 passes respectively The operations of these algorithms mimic those of Zelke’s and McGregor’s respective algorithms for MWM the novelty lies in the analysis for the MSM setting In fact we identify a general framework for MWM algorithms that allows this kind of adaptation to the broader setting of MSM Our framework is not specific to matchings Rather we identify a general pattern for algorithms that maximize linear weight functions over “independent sets” and prove that such algorithms can be adapted to maximize a submodular function The notion of independence here is very general in particular appealing to known weightmaximization algorithms we obtain results for submodular maximization over hypermatchings in hypergraphs as well as independent sets in the intersection of multiple matroids
Keywords: