Journal
MATHEMATICAL PROGRAMMING
Volume 154, Issue 1-2, Pages 225-247Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-015-0900-7
Keywords
-
Categories
Funding
- NSF [1217375]
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1217375] Funding Source: National Science Foundation
Ask authors/readers for more resources
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), which is in turn a generalization of maximum cardinality matching. We give two incomparable algorithms for this problem with space usage falling in the semi-streaming range-they store only edges, using working memory-that achieve approximation ratios of 7.75 in a single pass and in 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 weight-maximization algorithms, we obtain results for submodular maximization over hypermatchings in hypergraphs as well as independent sets in the intersection of multiple matroids.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available