Competitive Weighted Matching in Transversal Matroids
Tóm tắt
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.
Tài liệu tham khảo
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)