1 Search Results for "Wu, Jinzhao"


Document
Track A: Algorithms, Complexity and Games
Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications

Authors: Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)


Abstract
With a wide range of applications, stochastic matching problems have been studied in different models, including prophet inequality, Query-Commit, and Price-of-Information. While there have been recent breakthroughs in all these settings for bipartite graphs, few non-trivial results are known for general graphs. In this paper, we study the random order vertex arrival contention resolution scheme for matching in general graphs, which is inspired by the recent work of Ezra et al. (EC 2020). We design an 8/15-selectable batched RCRS for matching and apply it to achieve 8/15-competitive/approximate algorithms for all the three models. Our results are the first non-trivial results for random order prophet matching and Price-of-Information matching in general graphs. For the Query-Commit model, our result substantially improves upon the 0.501 approximation ratio by Tang et al. (STOC 2020). We also show that no batched RCRS for matching can be better than 1/2+1/(2e²) ≈ 0.567-selectable.

Cite as

Hu Fu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, and Qianfan Zhang. Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 68:1-68:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{fu_et_al:LIPIcs.ICALP.2021.68,
  author =	{Fu, Hu and Tang, Zhihao Gavin and Wu, Hongxun and Wu, Jinzhao and Zhang, Qianfan},
  title =	{{Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{68:1--68:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.68},
  URN =		{urn:nbn:de:0030-drops-141376},
  doi =		{10.4230/LIPIcs.ICALP.2021.68},
  annote =	{Keywords: Matching, Contention Resolution Scheme, Price of Information, Query-Commit}
}
  • Refine by Author
  • 1 Fu, Hu
  • 1 Tang, Zhihao Gavin
  • 1 Wu, Hongxun
  • 1 Wu, Jinzhao
  • 1 Zhang, Qianfan

  • Refine by Classification
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 Contention Resolution Scheme
  • 1 Matching
  • 1 Price of Information
  • 1 Query-Commit

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail