File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: How to match when all vertices arrive online

TitleHow to match when all vertices arrive online
Authors
Issue Date2018
PublisherACM 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?
AbstractWe 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 Identifierhttp://hdl.handle.net/10722/260345
ISBN
ISI Accession Number ID

 

DC FieldValueLanguage
dc.contributor.authorHuang, Z-
dc.contributor.authorKang, N-
dc.contributor.authorTang, Z-
dc.contributor.authorWu, X-
dc.contributor.authorZhang, Y-
dc.contributor.authorZhu, X-
dc.date.accessioned2018-09-14T08:40:09Z-
dc.date.available2018-09-14T08:40:09Z-
dc.date.issued2018-
dc.identifier.citationProceedings 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.isbn9781450355599-
dc.identifier.urihttp://hdl.handle.net/10722/260345-
dc.description.abstractWe 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.languageeng-
dc.publisherACM Press.-
dc.relation.ispartofProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing-
dc.titleHow to match when all vertices arrive online-
dc.typeConference_Paper-
dc.identifier.emailHuang, Z: zhiyi@cs.hku.hk-
dc.identifier.authorityHuang, Z=rp01804-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1145/3188745.3188858-
dc.identifier.hkuros290748-
dc.identifier.spage17-
dc.identifier.epage29-
dc.identifier.isiWOS:000458175600004-
dc.publisher.placeNew York, NY-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats