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 ...
Roginski, Jonathan W. (Monterey, CA; Naval Postgraduate School, 2018-06);This research provides an innovative approach to identifying the influence of vertices on the topology of a graph by introducing and exploring the neighbor matrix and distance centrality. The neighbor matrix depicts the ...