MathDB

Brubach–Sankararaman–Srinivasan–Xu sampling conjecture for hypergraph matchings

About 6 years old · traced to

Let H=(V,E)H=(V,E) be a hypergraph, let w∈R≥0Ew\in\mathbb{R}_{\geq 0}^E be edge weights, and let x∈[0,1]Ex\in[0,1]^E be a fractional matching, meaning that

∑e∈δ(v)x(e)≤1for every v∈V,\sum_{e\in\delta(v)}x(e)\leq 1\qquad\text{for every }v\in V,

where δ(v)=e∈E:v∈e\delta(v)=\\{e\in E:v\in e\\}. Brubach–Sankararaman–Srinivasan–Xu conjecture. It is possible to efficiently sample a matching M⊆EM\subseteq E from a distribution such that every edge e∈Ee\in E satisfies

Pr⁡[e∈M]≥x(e)∣e∣−1+1∣e∣.\Pr[e\in M]\geq\frac{x(e)}{|e|-1+\frac{1}{|e|}}.

This is a distributional and algorithmic strengthening of the Füredi–Kahn–Seymour guarantee. The source describes related weaker bounds and states that the conjecture remains unresolved.

References

Primary source

Georg Anegg, Haris Angelidakis and Rico Zenklusen, “Simpler and Stronger Approaches for Non-Uniform Hypergraph Matching and the Füredi, Kahn, and Seymour Conjecture”, arXiv:2009.00697 (2020).

approximation-algorithmshypergraph-matchingrandomized-algorithms
Posted

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.