Competitive Weighted Matching in Transversal Matroids
Dimitrov, N. B.
MetadataShow full item record
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.
The article of record as published may be located at 10.1007/978-3-540-70575-8_33
Showing items related by title, author, creator and subject.
Gillespie, Clark McKinley, Jr. (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 ...
Fletcher, Douglas M. (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 ...
Gera, Ralucca; Ping, Zhang (2007);An oriented graph is 2-stratified if its vertex set is partitioned into two classes, where the vertices in one class are colored red and those in the other class are colored blue. Let H be a 2-stratified oriented graph ...