Competitive Weighted Matching in Transversal Matroids
Competitive Weighted Matching in Transversal Matroids
复制标题
DOI：
10.1007/s00453-010-9457-2
复制
发表时间：
2008-07
期刊：
影响因子：
1.1
通讯作者：
N. Dimitrov;C. Plaxton
中科院分区：
文献类型：
--
作者：
N. Dimitrov;C. Plaxton
考虑一个具有一组左顶点和一组右顶点的二部图。与同一左顶点相邻的所有边具有相同的权重。我们提出了一个算法，给定右顶点的集合和左顶点的数目，处理左顶点的均匀随机置换，一次一个左顶点。在处理一个特定的左顶点时，算法要么永久地将左顶点匹配到一个迄今为止不匹配的右顶点，要么决定永远不匹配左顶点。我们的算法返回的匹配的权重是在一个恒定的因素，最大权重匹配，概括Babaioff等人的最近的结果。
Consider a bipartite graph with a set of left-vertices and a set of right-vertices. All the edges adjacent to the same left-vertex have the same weight. We present an algorithm that, given the set of right-vertices and the number of left-vertices, processes a uniformly random permutation of the left-vertices, one left-vertex at a time. In processing a particular left-vertex, the algorithm either permanently matches the left-vertex to a thus-far unmatched right-vertex, or decides never to match the left-vertex. The weight of the matching returned by our algorithm is within a constant factor of that of a maximum weight matching, generalizing the recent results of Babaioff et al.