论文标题
非均匀超图匹配的简单和强大方法以及Füredi，Kahn和Seymour猜想
Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture
论文作者
论文摘要
Füredi，Kahn和Seymour（1993）在非均匀的超图形匹配的情况下，有一个众所周知的猜想状态，对于任何具有边缘重量$ W $的超图，都存在匹配的$ m $，使得不等式$ \ sum_ {e \ in m} g（e）w（e）w（e）w（e）w（e）保留$ g（e）= | e | -1+ \ frac {1} {| e |} $，其中$ \ mathrm {opt} _ {\ mathrm {lp}} $表示规范lp sleake的最佳值。 虽然猜想仍然保持开放，但最近的最强结果是由Brubach，Sankararaman，Srinivasan和Xu（2020）（2020年）获得的---基于Bansal，Gupta，Gupta，Li，Mestre，Nagarajan和Rudra（2012） - 与Aforemention Inderementimentimentimentimentimentimentimentimentimentimentimentimentimentimentimentions-Equeartions-Equementions-Equoreperions-Equoreptions-the Importions-Equorentionals-Equementions--- $ g（e）= | e |+o（| e | \ exp（ - | e |））$。 实际上，他们的方法在更通用的采样设置中起作用，在此，给定一个规范LP放松的点$ x $，任务是有效地品尝匹配的$ m $，其中包含每个边缘$ e $，概率至少$ \ frac {x（e）}} {g（e）} $。 我们提出更简单，易于分析的程序，从而改善结果。更准确地说，对于任何解决方案$ x $，我们向规范LP介绍了基于Brubach等人的指数时钟的简单算法，以实现$ g（e）= | e | - （| e | - 1）x（e）$。 除了$ g $的略有改进外，我们的技术还可以打开攻击原始猜想的新方法。 此外，我们提供了一个简短且可以说的优雅分析，表明对猜想的原始设置的天然贪婪方法表明，相同的$ g（e）= | e | - （| e | -1）x（e）x（e）$，甚至对于更通用的hypergraph $ b $ b $ - 匹配问题。
A well-known conjecture of Füredi, Kahn, and Seymour (1993) on non-uniform hypergraph matching states that for any hypergraph with edge weights $w$, there exists a matching $M$ such that the inequality $\sum_{e\in M} g(e) w(e) \geq \mathrm{OPT}_{\mathrm{LP}}$ holds with $g(e)=|e|-1+\frac{1}{|e|}$, where $\mathrm{OPT}_{\mathrm{LP}}$ denotes the optimal value of the canonical LP relaxation. While the conjecture remains open, the strongest result towards it was very recently obtained by Brubach, Sankararaman, Srinivasan, and Xu (2020)---building on and strengthening prior work by Bansal, Gupta, Li, Mestre, Nagarajan, and Rudra (2012)---showing that the aforementioned inequality holds with $g(e)=|e|+O(|e|\exp(-|e|))$. Actually, their method works in a more general sampling setting, where, given a point $x$ of the canonical LP relaxation, the task is to efficiently sample a matching $M$ containing each edge $e$ with probability at least $\frac{x(e)}{g(e)}$. We present simpler and easy-to-analyze procedures leading to improved results. More precisely, for any solution $x$ to the canonical LP, we introduce a simple algorithm based on exponential clocks for Brubach et al.'s sampling setting achieving $g(e)=|e|-(|e|-1)x(e)$. Apart from the slight improvement in $g$, our technique may open up new ways to attack the original conjecture. Moreover, we provide a short and arguably elegant analysis showing that a natural greedy approach for the original setting of the conjecture shows the inequality for the same $g(e)=|e|-(|e|-1)x(e)$ even for the more general hypergraph $b$-matching problem.
