The asymptotic robustness limit conjecture for matchings

From papers

Let GG range over graphs. For each KNK\in\mathbb{N}, let αK\alpha_K denote the smallest KK-asymptotic robustness ratio over all graphs, and let α(G)\alpha^*(G) denote the randomized robustness ratio of GG. Asymptotic robustness limit conjecture.

limKαK=infGα(G)\lim_{K \rightarrow \infty} \alpha_{K} = \inf_{G} \alpha^*(G)

This conjecture would follow from a sparsification result for arbitrary randomized matchings, extending the constant-support sparsification established for the distributions used earlier in the paper. It asserts that the limiting deterministic asymptotic robustness ratio equals the worst-case randomized robustness ratio.

Progress summary

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

Sources & referencesView supporting material

Primary source

Jannik Matuschke, Martin Skutella and José A. Soto, “Robust randomized matchings”, arXiv:1705.06631 (2017).

Solutions 0

No solutions have been posted yet.