首页    期刊浏览 2024年11月28日 星期四
登录注册

文章基本信息

  • 标题:A Simple Augmentation Method for Matchings with Applications to Streaming Algorithms
  • 本地全文:下载
  • 作者:Christian Konrad
  • 期刊名称:LIPIcs : Leibniz International Proceedings in Informatics
  • 电子版ISSN:1868-8969
  • 出版年度:2018
  • 卷号:117
  • 页码:1-16
  • DOI:10.4230/LIPIcs.MFCS.2018.74
  • 出版社:Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
  • 摘要:Given a graph G, it is well known that any maximal matching M in G is at least half the size of a maximum matching M^*. In this paper, we show that if G is bipartite, then running the Greedy matching algorithm on a sampled subgraph of G produces enough additional edges that can be used to augment M such that the resulting matching is of size at least (2 - sqrt{2})|M^*| ~~ 0.5857 |M^*| (ignoring lower order terms) with high probability. The main applications of our method lie in the area of data streaming algorithms, where an algorithm performs few passes over the edges of an n-vertex graph while maintaining a memory of size O(n polylog n). Our method immediately yields a very simple two-pass algorithm for Maximum Bipartite Matching (MBM) with approximation factor 0.5857, which only runs the Greedy matching algorithm in each pass. This slightly improves on the much more involved 0.583-approximation algorithm of Esfandiari et al. [ICDMW 2016]. To obtain our main result, we combine our method with a residual sparsity property of the random order Greedy algorithm and give a one-pass random order streaming algorithm for MBM with approximation factor 0.5395. This substantially improves upon the one-pass random order 0.505-approximation algorithm of Konrad et al. [APPROX 2012].
  • 关键词:Matchings; augmenting paths; streaming algorithms; random order
国家哲学社会科学文献中心版权所有