File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3326169
- Scopus: eid_2-s2.0-85069471846
- WOS: WOS:000476993900009
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals
Title | Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals |
---|---|
Authors | |
Keywords | online bipartite matching randomized primal-dual Vertex weighted Algorithms Mathematical techniques |
Issue Date | 2019 |
Publisher | Association for Computing Machinery, Inc. |
Citation | ACM Transactions on Algorithms, 2019, v. 15 n. 3, p. article no. 18:1-15 How to Cite? |
Abstract | We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and we prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching problem when online vertices arrive in random order. Our result shows that random arrivals help beating the 1-1/e barrier even in the vertex-weighted case. We build on the randomized primal-dual framework by Devanur et al. (SODA 2013) and design a two dimensional gain sharing function, which depends not only on the rank of the offline vertex, but also on the arrival time of the online vertex. To our knowledge, this is the first competitive ratio strictly larger than 1-1/e for an online bipartite matching problem achieved under the randomized primal-dual framework. Our algorithm has a natural interpretation that offline vertices offer a larger portion of their weights to the online vertices as time increases, and each online vertex matches the neighbor with the highest offer at its arrival. |
Persistent Identifier | http://hdl.handle.net/10722/273144 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 1.555 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Tang, ZG | - |
dc.contributor.author | Wu, X | - |
dc.contributor.author | ZHANG, Y | - |
dc.date.accessioned | 2019-08-06T09:23:21Z | - |
dc.date.available | 2019-08-06T09:23:21Z | - |
dc.date.issued | 2019 | - |
dc.identifier.citation | ACM Transactions on Algorithms, 2019, v. 15 n. 3, p. article no. 18:1-15 | - |
dc.identifier.issn | 1549-6325 | - |
dc.identifier.uri | http://hdl.handle.net/10722/273144 | - |
dc.description.abstract | We introduce a weighted version of the ranking algorithm by Karp et al. (STOC 1990), and we prove a competitive ratio of 0.6534 for the vertex-weighted online bipartite matching problem when online vertices arrive in random order. Our result shows that random arrivals help beating the 1-1/e barrier even in the vertex-weighted case. We build on the randomized primal-dual framework by Devanur et al. (SODA 2013) and design a two dimensional gain sharing function, which depends not only on the rank of the offline vertex, but also on the arrival time of the online vertex. To our knowledge, this is the first competitive ratio strictly larger than 1-1/e for an online bipartite matching problem achieved under the randomized primal-dual framework. Our algorithm has a natural interpretation that offline vertices offer a larger portion of their weights to the online vertices as time increases, and each online vertex matches the neighbor with the highest offer at its arrival. | - |
dc.language | eng | - |
dc.publisher | Association for Computing Machinery, Inc. | - |
dc.relation.ispartof | ACM Transactions on Algorithms | - |
dc.rights | ACM Transactions on Algorithms. Copyright © Association for Computing Machinery, Inc. | - |
dc.rights | ©ACM, YYYY. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in PUBLICATION, {VOL#, ISS#, (DATE)} http://doi.acm.org/10.1145/nnnnnn.nnnnnn | - |
dc.subject | online bipartite matching | - |
dc.subject | randomized primal-dual | - |
dc.subject | Vertex weighted | - |
dc.subject | Algorithms | - |
dc.subject | Mathematical techniques | - |
dc.title | Online Vertex-Weighted Bipartite Matching: Beating 1-1/e with Random Arrivals | - |
dc.type | Article | - |
dc.identifier.email | Huang, Z: zhiyi@cs.hku.hk | - |
dc.identifier.authority | Huang, Z=rp01804 | - |
dc.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/3326169 | - |
dc.identifier.scopus | eid_2-s2.0-85069471846 | - |
dc.identifier.hkuros | 299978 | - |
dc.identifier.volume | 15 | - |
dc.identifier.issue | 3 | - |
dc.identifier.spage | article no. 18:1 | - |
dc.identifier.epage | 15 | - |
dc.identifier.isi | WOS:000476993900009 | - |
dc.publisher.place | United States | - |
dc.identifier.issnl | 1549-6325 | - |