Competitive Weighted Matching in Transversal Matroids

被引：28

作者：

Dimitrov, Nedialko B. ^{[1
]}

Plaxton, C. Greg ^{[2
]}

机构：

[1] USN, Postgrad Sch, Dept Operat Res, Monterey, CA 93943 USA

[2] Univ Texas Austin, Dept Comp Sci, Austin, TX 78701 USA

来源：

ALGORITHMICA | 2012年 / 62卷 / 1-2期

关键词：

Matching; Online algorithm; Secretary problem; Transversal matroid;

D O I：

10.1007/s00453-010-9457-2

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

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.

引用

页码：333 / 348

页数：16