论文标题
关于HyperGraph匹配和Füredi-Kahn-Seymour的一些评论
Some remarks on hypergraph matching and the Füredi-Kahn-Seymour conjecture
论文作者
论文摘要
Füredi，Kahn和Seymour（1993）的经典猜想指出，鉴于具有非负边缘的任何超图$ w（e）$，存在匹配的$ m $，因此$ \ sum_ {e \ in m}（| e | e | e | -1+1+1/| e | e | e | e |）我们表明，对等级3超图是正确的，并且是通过天然迭代的圆形算法实现的。虽然一般的猜想保持开放，但我们提供了几个新的改进范围。特别是，我们表明迭代舍入算法给出$ \ sum_ {e \ in m}（| e |-Δ（e））\，w（e）\ geq w^*$，其中$Δ（e）= |/（e | e | e | e | e | e | e |^2+| e | -1）$，改善了$ sum_ | e | e | e | \ geq w^*$。
A classic conjecture of Füredi, Kahn and Seymour (1993) states that given any hypergraph with non-negative edge weights $w(e)$, there exists a matching $M$ such that $\sum_{e \in M} (|e|-1+1/|e|)\, w(e) \geq w^*$, where $w^*$ is the value of an optimum fractional matching. We show the conjecture is true for rank-3 hypergraphs, and is achieved by a natural iterated rounding algorithm. While the general conjecture remains open, we give several new improved bounds. In particular, we show that the iterated rounding algorithm gives $\sum_{e \in M} (|e|-δ(e))\, w(e) \geq w^*$, where $δ(e) = |e|/(|e|^2+|e|-1)$, improving upon the baseline guarantee of $\sum_{e \in M} |e|\,w(e) \geq w^*$.
