Online Transversal Matroid

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.

This problem can be viewed as a generalization of the classic secretary problem by viewing the left-vertices as job candidates and the right-vertices as job openings. The edges in the bipartite graph then signify that a particular candidate is elligable for the corresponding job opening. The problem also has connections to online auctions, since finding a near-optimal weight matching can be viewed as getting near-optimal revenue when selling the right-vertices.

You can also view a talk on the same research.

Papers

Nedialko B. Dimitrov and C. Greg Plaxton. Competitive Weighted Matching in Transversal Matroids. Algorithmica, October 2010, doi: 10.1007/s00453-010-9457-2

Nedialko B. Dimitrov and C. Greg Plaxton. Competitive Weighted Matching in Transversal Matroids. Proceedings of the 35th annual International Colloquium on Automata, Languages and Programming (ICALP08), July, 2008

Nedialko B. Dimitrov and C. Greg Plaxton. Competitive Weighted Matching in Transversal Matroids. UT Austin, Technical Report T-08-03, January, 2008

Comments and Questions


Warning: Creating default object from empty value in /home/nedd/neddimitrov.org/modules/CGExtensions/CGExtensions.module.php on line 630
Add a comment

Add A Comment

Visual Captcha
Code in the picture:
Your Name(*):
Comment(*):
 


© Copyright 2004-2017 - Ned Dimitrov