专栏首页算法和应用关于无意识匹配问题
原创

关于无意识匹配问题

作者:Zhihao Gavin Tang,Xiaowei Wu,Yuhao Zhang

摘要:关于无意识匹配问题的扰动扩散我们研究了不经意设置中的最大匹配问题,即该算法未知图的边集。在这对顶点的探针上显示出边缘的存在。此外,如果在两个探测顶点之间存在边缘,则边缘必须不可撤销地包括在匹配中。对于未加权图,Karp等人的术语{rankingf {Ranking}算法〜(STOC 1990)实现了二分图的近似比率为0.96,而对于一般图表则为0.526。对于顶点加权图,Chan等。 (TALG 2018)提出了a0.501近似算法。相比之下,边缘加权版本只承认Greedy的琐碎0.5近似值。

在本文中,我们提出了\ textsf {Perturbed Greedy}算法用于边缘加权遗忘匹配问题,并证明它达到了0.501的近似比率。此外,我们证明了我们的算法在非加权图上的近似比对于二分图是0.639,对于一般图是0.531。后者改进了Chan等人的最新结果。 (TALG 2018)。此外,我们的算法可以被视为\ textsf {Modified Randomized Greedy}(MRG)算法的健壮版本。通过暗示,我们的0.531近似比率作为MRG算法超出(1/2 +ε)范围的第一个分析。

原文标题:Perturbed Greedy on Oblivious Matching Problems

原文摘要:We study the maximum matching problem in the oblivious setting, i.e. the edge set of the graph is unknown to the algorithm. The existence of an edge is revealed upon the probe of this pair of vertices. Further, if an edge exists between two probed vertices, then the edge must be included in the matching irrevocably. For unweighted graphs, the \textsf{Ranking} algorithm by Karp et al.~(STOC 1990) achieves approximation ratios0.696for bipartite graphs and0.526for general graphs. For vertex-weighted graphs, Chan et al. (TALG 2018) proposed a0.501-approximate algorithm. In contrast, the edge-weighted version only admits the trivial0.5-approximation by Greedy.

In this paper, we propose the \textsf{Perturbed Greedy} algorithm for the edge-weighted oblivious matching problem and prove that it achieves a0.501approximation ratio. Besides, we show that the approximation ratio of our algorithm on unweighted graphs is0.639for bipartite graphs, and0.531for general graphs. The later improves the state-of-the-art result by Chan et al. (TALG 2018). Furthermore, our algorithm can be regarded as a robust version of the \textsf{Modified Randomized Greedy} (MRG) algorithm. By implication, our0.531approximation ratio serves as the first analysis of the MRG algorithm beyond the(1/2+ϵ)regime.

地址:https://arxiv.org/abs/1907.05135

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Googol的双面博弈与基于样本的先知不等式

    作者:José Correa,Andrés Cristi,Boris Epstein,José A. Soto

    罗大琦
  • 利用局部正确性设计完美仿真算法

    摘要:考虑一种随机算法,该算法使用递归从分布中精确地绘制样本。这种算法被称为完美模拟,这里建立各种用于构建这种算法的方法都源自相同的结果:完美模拟的基本定理(F...

    罗大琦
  • 伸展树的先序和后序

    摘要:设T是二叉搜索树。我们证明了关于Splay算法行为的两个结果(Sleator和Tarjan 1985)。我们的第一个结果是通过按照T的预订或T的后序的顺序...

    罗大琦
  • Playrix Codescapes Cup (Codeforces Round #413, rated, Div. 1 + Div. 2)(A.暴力,B.优先队列,C.dp乱搞)

    A. Carrot Cakes time limit per test:1 second memory limit per test:256 megabytes...

    Angel_Kitty
  • 【短道速滑四】Halcon的texture_laws算子自我研究

      Halcon里有个texture_laws 算子,最近实现了下,记录下相关细节。

    用户1138785
  • 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

    Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

    某些人
  • 【CodeForces 602C】H - Approximating a Constant Range(dijk)

    In Absurdistan, there are n towns (numbered 1 through n) and m bidirectional rai...

    饶文津
  • Ceph用户邮件列表Vol45-Issue3

    https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git/commit/?id=af5e5...

    用户2772802
  • Code force-CodeCraft-20 (Div. 2) D. Nash Matrix 详解(DFS构造)

    D. Nash Matrix time limit per test2 seconds memory limit per test256 megabytes...

    风骨散人Chiam
  • universe-starter-agent

    The codebase implements a starter agent that can solve a number of universe envi...

    用户1908973

扫码关注云+社区

领取腾讯云代金券