期刊
MATHEMATICAL PROGRAMMING
卷 154, 期 1-2, 页码 225-247出版社
SPRINGER HEIDELBERG
DOI: 10.1007/s10107-015-0900-7
关键词
-
类别
资金
- NSF [1217375]
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1217375] Funding Source: National Science Foundation
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据