File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783319080161_22
 Scopus: eid_2s2.084903592047
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Near Optimal Algorithms for Online Maximum Weighted bMatching
Title  Near Optimal Algorithms for Online Maximum Weighted bMatching 

Authors  
Issue Date  2014 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 8th International Frontiers of Algorithmics Workshop (FAW 2014), Zhangjiajie, China, 2830 June 2014. In Lecture Notes in Computer Science, 2014, v. 8497, p. 240251 How to Cite? 
Abstract  We study the online maximum weighted bmatching 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 GreedyRT 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 GreedyRT is near optimal. Deterministic algorithms are also considered and we present a near optimal algorithm GreedyD 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 twosided vertexweighted matching problem, and give a modification of the randomized algorithm GreedyRT called Greedy v RT specially for this variant. We show that Greedy v RT is also near optimal. 
Description  Lecture Notes in Computer Science, vol. 8497 entitled: Frontiers in Algorithmics: 8th International Workshop, FAW 2014, Zhangjiajie, China, June 2830, 2014: proceedings 
Persistent Identifier  http://hdl.handle.net/10722/203639 
ISSN  2005 Impact Factor: 0.302 2015 SCImago Journal Rankings: 0.252 
DC Field  Value  Language 

dc.contributor.author  Ting, HF  en_US 
dc.contributor.author  Xiang, X  en_US 
dc.date.accessioned  20140919T15:49:09Z   
dc.date.available  20140919T15:49:09Z   
dc.date.issued  2014  en_US 
dc.identifier.citation  The 8th International Frontiers of Algorithmics Workshop (FAW 2014), Zhangjiajie, China, 2830 June 2014. In Lecture Notes in Computer Science, 2014, v. 8497, p. 240251  en_US 
dc.identifier.issn  03029743   
dc.identifier.uri  http://hdl.handle.net/10722/203639   
dc.description  Lecture Notes in Computer Science, vol. 8497 entitled: Frontiers in Algorithmics: 8th International Workshop, FAW 2014, Zhangjiajie, China, June 2830, 2014: proceedings   
dc.description.abstract  We study the online maximum weighted bmatching 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 GreedyRT 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 GreedyRT is near optimal. Deterministic algorithms are also considered and we present a near optimal algorithm GreedyD 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 twosided vertexweighted matching problem, and give a modification of the randomized algorithm GreedyRT called Greedy v RT specially for this variant. We show that Greedy v RT is also near optimal.   
dc.language  eng  en_US 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/   
dc.relation.ispartof  Lecture Notes in Computer Science  en_US 
dc.rights  The original publication is available at www.springerlink.com   
dc.title  Near Optimal Algorithms for Online Maximum Weighted bMatching  en_US 
dc.type  Conference_Paper  en_US 
dc.identifier.email  Ting, HF: hfting@cs.hku.hk  en_US 
dc.identifier.authority  Ting, HF=rp00177  en_US 
dc.identifier.doi  10.1007/9783319080161_22   
dc.identifier.scopus  eid_2s2.084903592047   
dc.identifier.hkuros  238608  en_US 
dc.identifier.volume  8497   
dc.identifier.spage  240   
dc.identifier.epage  251   
dc.publisher.place  Germany   