File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Near Optimal Algorithms for Online Maximum Weighted b-Matching

TitleNear Optimal Algorithms for Online Maximum Weighted b-Matching
Authors
Issue Date2014
PublisherSpringer 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, 28-30 June 2014. In Lecture Notes in Computer Science, 2014, v. 8497, p. 240-251 How to Cite?
AbstractWe 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.
DescriptionLecture Notes in Computer Science, vol. 8497 entitled: Frontiers in Algorithmics: 8th International Workshop, FAW 2014, Zhangjiajie, China, June 28-30, 2014: proceedings
Persistent Identifierhttp://hdl.handle.net/10722/203639
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorTing, HFen_US
dc.contributor.authorXiang, Xen_US
dc.date.accessioned2014-09-19T15:49:09Z-
dc.date.available2014-09-19T15:49:09Z-
dc.date.issued2014en_US
dc.identifier.citationThe 8th International Frontiers of Algorithmics Workshop (FAW 2014), Zhangjiajie, China, 28-30 June 2014. In Lecture Notes in Computer Science, 2014, v. 8497, p. 240-251en_US
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/203639-
dc.descriptionLecture Notes in Computer Science, vol. 8497 entitled: Frontiers in Algorithmics: 8th International Workshop, FAW 2014, Zhangjiajie, China, June 28-30, 2014: proceedings-
dc.description.abstractWe 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.-
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.titleNear Optimal Algorithms for Online Maximum Weighted b-Matchingen_US
dc.typeConference_Paperen_US
dc.identifier.emailTing, HF: hfting@cs.hku.hken_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.identifier.doi10.1007/978-3-319-08016-1_22-
dc.identifier.scopuseid_2-s2.0-84903592047-
dc.identifier.hkuros238608en_US
dc.identifier.volume8497-
dc.identifier.spage240-
dc.identifier.epage251-
dc.publisher.placeGermany-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats