File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-319-08016-1_22
- Scopus: eid_2-s2.0-84903592047
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Near Optimal Algorithms for Online Maximum Weighted b-Matching
Title | Near Optimal Algorithms for Online Maximum Weighted b-Matching |
---|---|
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, 28-30 June 2014. In Lecture Notes in Computer Science, 2014, v. 8497, p. 240-251 How to Cite? |
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. |
Description | Lecture Notes in Computer Science, vol. 8497 entitled: Frontiers in Algorithmics: 8th International Workshop, FAW 2014, Zhangjiajie, China, June 28-30, 2014: proceedings |
Persistent Identifier | http://hdl.handle.net/10722/203639 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Ting, HF | en_US |
dc.contributor.author | Xiang, X | en_US |
dc.date.accessioned | 2014-09-19T15:49:09Z | - |
dc.date.available | 2014-09-19T15:49:09Z | - |
dc.date.issued | 2014 | en_US |
dc.identifier.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 | en_US |
dc.identifier.issn | 0302-9743 | - |
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 28-30, 2014: proceedings | - |
dc.description.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. | - |
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 b-Matching | 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/978-3-319-08016-1_22 | - |
dc.identifier.scopus | eid_2-s2.0-84903592047 | - |
dc.identifier.hkuros | 238608 | en_US |
dc.identifier.volume | 8497 | - |
dc.identifier.spage | 240 | - |
dc.identifier.epage | 251 | - |
dc.publisher.place | Germany | - |
dc.identifier.issnl | 0302-9743 | - |