File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3390890
- Scopus: eid_2-s2.0-85087162239
- WOS: WOS:000582594800004
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Fully Online Matching
Title | Fully Online Matching |
---|---|
Authors | |
Keywords | Graphic methods Bipartite graphs Cardinality matching Competitive ratio On-line algorithms |
Issue Date | 2020 |
Publisher | Association for Computing Machinery. The Journal's web site is located at http://jacm.acm.org/ |
Citation | Journal of the ACM, 2020, v. 67 n. 3, p. article no. 17 How to Cite? |
Abstract | We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors’ arrivals. If a vertex remains unmatched until its deadline, then the algorithm must irrevocably either match it to an unmatched neighbor or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, and so on.
We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step toward solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, then we show a tight competitive ratio ≈0.5671 of Ranking. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317 < 1- 1/e-competitive in our model, even for bipartite graphs. |
Persistent Identifier | http://hdl.handle.net/10722/284233 |
ISSN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Kang, N | - |
dc.contributor.author | Tang, ZG | - |
dc.contributor.author | Wu, X | - |
dc.contributor.author | ZHANG, Y | - |
dc.contributor.author | ZHU, X | - |
dc.date.accessioned | 2020-07-20T05:57:07Z | - |
dc.date.available | 2020-07-20T05:57:07Z | - |
dc.date.issued | 2020 | - |
dc.identifier.citation | Journal of the ACM, 2020, v. 67 n. 3, p. article no. 17 | - |
dc.identifier.issn | 1535-9921 | - |
dc.identifier.uri | http://hdl.handle.net/10722/284233 | - |
dc.description.abstract | We introduce a fully online model of maximum cardinality matching in which all vertices arrive online. On the arrival of a vertex, its incident edges to previously arrived vertices are revealed. Each vertex has a deadline that is after all its neighbors’ arrivals. If a vertex remains unmatched until its deadline, then the algorithm must irrevocably either match it to an unmatched neighbor or leave it unmatched. The model generalizes the existing one-sided online model and is motivated by applications including ride-sharing platforms, real-estate agency, and so on. We show that the Ranking algorithm by Karp et al. (STOC 1990) is 0.5211-competitive in our fully online model for general graphs. Our analysis brings a novel charging mechanic into the randomized primal dual technique by Devanur et al. (SODA 2013), allowing a vertex other than the two endpoints of a matched edge to share the gain. To our knowledge, this is the first analysis of Ranking that beats 0.5 on general graphs in an online matching problem, a first step toward solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, then we show a tight competitive ratio ≈0.5671 of Ranking. Finally, we prove that the fully online model is strictly harder than the previous model as no online algorithm can be 0.6317 < 1- 1/e-competitive in our model, even for bipartite graphs. | - |
dc.language | eng | - |
dc.publisher | Association for Computing Machinery. The Journal's web site is located at http://jacm.acm.org/ | - |
dc.relation.ispartof | Journal of the ACM | - |
dc.rights | Journal of the ACM. Copyright © Association for Computing Machinery. | - |
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 | Graphic methods | - |
dc.subject | Bipartite graphs | - |
dc.subject | Cardinality matching | - |
dc.subject | Competitive ratio | - |
dc.subject | On-line algorithms | - |
dc.title | Fully Online Matching | - |
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.description.nature | link_to_subscribed_fulltext | - |
dc.identifier.doi | 10.1145/3390890 | - |
dc.identifier.scopus | eid_2-s2.0-85087162239 | - |
dc.identifier.hkuros | 310908 | - |
dc.identifier.volume | 67 | - |
dc.identifier.issue | 3 | - |
dc.identifier.spage | article no. 17 | - |
dc.identifier.epage | article no. 17 | - |
dc.identifier.isi | WOS:000582594800004 | - |
dc.publisher.place | United States | - |