Competitive Weighted Matching in Transversal Matroids
Loading...
Authors
Dimitrov, N. B.
Plaxton, C.G.
Subjects
Advisors
Date of Issue
2010-09
Date
September 2010
Publisher
Language
Abstract
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.
Type
Description
The article of record as published may be located at 10.1007/978-3-540-70575-8_33
Series/Report No
Department
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Algorithmica, 1-16, September 2010
Distribution Statement
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.