کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435667 | 689924 | 2015 | 10 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching Near optimal algorithms for online maximum edge-weighted b-matching and two-sided vertex-weighted b-matching](/preview/png/435667.png)
This paper studies the online maximum edge-weighted b -matching problem. The input of the problem is a weighted bipartite graph G=(L,R,E,w)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. The objective is to maximize the total weight of the matching edges. We give a randomized algorithm Greedy-RT for this problem, and show that its competitive ratio is Ω(1∏j=1log⁎wmax−1log(j)wmax) where wmaxwmax is an upper bound on the edge weights, which may not be known ahead of time. We can improve the competitive ratio to Ω(1logwmax) if wmaxwmax is known to the algorithm when it starts. We also derive an upper bound O(1logwmax) on the competitive ratio, suggesting that Greedy-RT is near optimal. We also consider deterministic algorithms; we present a near optimal algorithm Greedy-D which has competitive ratio 11+2ξ(wmax+1)1ξ, where ξ=min{b,⌈ln(1+wmax)⌉}ξ=min{b,⌈ln(1+wmax)⌉}.We also study a variant of the problem called online maximum two-sided vertex-weighted b-matching problem, and give a modification of the randomized algorithm Greedy-RT called Greedy-vRT for this variant. We show that the competitive ratio of Greedy-vRT is also near optimal.
Journal: Theoretical Computer Science - Volume 607, Part 2, 23 November 2015, Pages 247–256