The asymptotic robustness limit conjecture for matchings
The asymptotic robustness limit conjecture for matchings
Let range over graphs. For each , let denote the smallest -asymptotic robustness ratio over all graphs, and let denote the randomized robustness ratio of . Asymptotic robustness limit conjecture.
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
Sign in to submit a solution.
No solutions have been posted yet.