File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1145/3188745.3188858
- Scopus: eid_2-s2.0-85049895116
- WOS: WOS:000458175600004
Supplementary
- Citations:
- Appears in Collections:
Conference Paper: How to match when all vertices arrive online
Title | How to match when all vertices arrive online |
---|---|
Authors | |
Keywords | Fully online matching Randomized primal-dual |
Issue Date | 2018 |
Publisher | ACM Press. |
Citation | Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), Los Angeles, CA, USA, 25-29 June 2018, p. 17-29 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, the algorithm must then 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, etc. 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 towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. 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/260345 |
ISBN | |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | - |
dc.contributor.author | Kang, N | - |
dc.contributor.author | Tang, Z | - |
dc.contributor.author | Wu, X | - |
dc.contributor.author | Zhang, Y | - |
dc.contributor.author | Zhu, X | - |
dc.date.accessioned | 2018-09-14T08:40:09Z | - |
dc.date.available | 2018-09-14T08:40:09Z | - |
dc.date.issued | 2018 | - |
dc.identifier.citation | Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), Los Angeles, CA, USA, 25-29 June 2018, p. 17-29 | - |
dc.identifier.isbn | 9781450355599 | - |
dc.identifier.uri | http://hdl.handle.net/10722/260345 | - |
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, the algorithm must then 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, etc. 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 towards solving the open problem by Karp et al. (STOC 1990) about the optimality of Ranking on general graphs. If the graph is bipartite, we show that the competitive ratio of Ranking is between 0.5541 and 0.5671. 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 | ACM Press. | - |
dc.relation.ispartof | Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | - |
dc.subject | Fully online matching | - |
dc.subject | Randomized primal-dual | - |
dc.title | How to match when all vertices arrive online | - |
dc.type | Conference_Paper | - |
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/3188745.3188858 | - |
dc.identifier.scopus | eid_2-s2.0-85049895116 | - |
dc.identifier.hkuros | 290748 | - |
dc.identifier.spage | 17 | - |
dc.identifier.epage | 29 | - |
dc.identifier.isi | WOS:000458175600004 | - |
dc.publisher.place | New York, NY | - |