Near Optimal Algorithms for Online Maximum Weighted b-Matching

Abstract

We study the online maximum weighted b-matching problem, in which the input is a bipartite graph G = (L,R,E, w). Vertices in R arrive online and each vertex in L can be matched to at most b vertices in R. Assume that the edge weights in G are no more than w max , which may not be known ahead of time. We show that a randomized algorithm Greedy-RT which has competitive ratio (Omega( frac{1}{prod_{j=1}^{log^* w_{max} - 1} log^{(j)} w_{max} })). We can improve the competitive ratio to (Omega(frac{1}{log w_{max}})) if w max is known to the algorithm when it starts. We also derive an upper bound (O(frac{1}{log w_{max}})) suggesting that Greedy-RT is near optimal. Deterministic algorithms are also considered and we present a near optimal algorithm Greedy-D which is ( frac{1}{1+2xi(w_{max}+1)^{frac{1}{xi}}})-competitive, where ξ = min {b, ⌈ln (1 + w max ) ⌉}. We propose a variant of the problem called online two-sided vertex-weighted matching problem, and give a modification of the randomized algorithm Greedy-RT called Greedy- v RT specially for this variant. We show that Greedy- v RT is also near optimal.