Competitive Weighted Matching in Transversal Matroids
2008_Dimitrov_Competetive_weighted.pdf (245.2Kb)Date
2010-09Metadata
Show full item recordAbstract
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.
Description
The article of record as published may be located at 10.1007/978-3-540-70575-8_33
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.Collections
Related items
Showing items related by title, author, creator and subject.
-
Locating absolute 2-centers of undirected graphs
(1968-12);This study analyzes the location of vertex and absolute 2-centers of an undirected graph. Under certain assumptions, these locations would be useful for determining the optimal positioning of emergency facilities such as ... -
Realizable triples in dominator colorings
(Monterey, California. Naval Postgraduate School, 2007-06);Given a graph G and its vertex set V(G), the chromatic number, Chi(G), represents the minimum number of colors required to color the vertices of G so that no two adjacent vertices have the same color. The domination number ... -
On stratification and domination in graphs
(2006);A graph G is 2-stratified if its vertex set is partitioned into two classes (each of which is a stratum or a color class), where the vertices in one class are colored red and those in the other class are colored blue. Let ...
