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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms, January 2007, pp. 434–443 (2008)
Birnbaum, B., Mathieu, C.: On-line bipartite matching made simple. SIGACT News 39, 80–87 (2008)
Borodin, A., El-Yaniv, R.: Online Computation and Competitive Analysis. Cambridge University Press, Cambridge (1998)
Ferguson, T.: Who solved the secretary problem? Stat. Sci. 4, 282–289 (1989)
Freeman, P.R.: The secretary problem and its extensions: a review. Int. Stat. Rev. 51, 189–206 (1983)
Karger, D.: Random sampling and greedy sparsification for matroid optimization problems. Math. Program. 82, 41–81 (1998)
Karp, R.M., Vazirani, U.V., Vazirani, V.V.: An optimal algorithm for on-line bipartite matching. In: Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, New York, NY, USA, May 1990, pp. 352–358 (1990)
Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, January 2005, pp. 630–631 (2005)
Korula, N., Pál, M.: Algorithms for secretary problems on graphs and hypergraphs. arXiv:0807.1139v1. July 2008
Lawler, E.: Combinatorial Optimization: Networks and Matroids. Dover, Mineola (2001)
Lindley, D.V.: Dynamic programming and decision theory. Appl. Stat. 10, 39–51 (1961)
Oxley, J.: What is a matroid? Cubo 5, 179–218 (2003)
Author information
Authors and Affiliations
Corresponding author
Additional information
N.B. Dimitrov is supported by an MCD Fellowship from the University of Texas at Austin.
C.G. Plaxton is supported by NSF Grants CCF–0635203 and ANI–0326001.
Rights and permissions
About this article
Cite this article
Dimitrov, N.B., Plaxton, C.G. Competitive Weighted Matching in Transversal Matroids. Algorithmica 62, 333–348 (2012). https://doi.org/10.1007/s00453-010-9457-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-010-9457-2