论文标题
迈向最佳竞争解决方案
Towards an Optimal Contention Resolution Scheme for Matchings
论文作者
论文摘要
在本文中，我们研究了匹配的争论解决方案。给定一个匹配的$ x $和一个随机套件$ r（x）$，其中每个边缘$ e $以概率$ x_e $独立出现，我们希望选择一个匹配的$ m \ subseteq r（x）$，使得$ \ pr [e \ in m mid e \ in mid e \ in R（x）\ geq c $ in r（x）] \ geq c $，对于$ c $ for $ c $，可能是$ c $。我们将这种选择方法称为$ C $平衡的争论解决方案。 我们的主要结果是（i）一个渐近（在$ \ | x \ | _ \ infty $中，为0）最佳$ \ simeq 0.544 $ - 平衡的争夺解决方案，以及（ii）$ 0.509 $ - 平衡的争议解决方案，用于双击匹配的竞争分辨率。据我们所知，这个结果首次建立了组合优化问题的任何自然放松，（i）离线和随机秩序在线争夺解决方案之间的分离，以及（ii）单调和非单调争议解决方案。我们还向组合分配问题提出了计划的应用，并讨论了与范德沃登（Van der Waerden）对偶然随机矩阵永久的猜想有关的一些开放问题。
In this paper, we study contention resolution schemes for matchings. Given a fractional matching $x$ and a random set $R(x)$ where each edge $e$ appears independently with probability $x_e$, we want to select a matching $M \subseteq R(x)$ such that $\Pr[e \in M \mid e \in R(x)] \geq c$, for $c$ as large as possible. We call such a selection method a $c$-balanced contention resolution scheme. Our main results are (i) an asymptotically (in the limit as $\|x\|_\infty$ goes to 0) optimal $\simeq 0.544$-balanced contention resolution scheme for general matchings, and (ii) a $0.509$-balanced contention resolution scheme for bipartite matchings. To the best of our knowledge, this result establishes for the first time, in any natural relaxation of a combinatorial optimization problem, a separation between (i) offline and random order online contention resolution schemes, and (ii) monotone and non-monotone contention resolution schemes. We also present an application of our scheme to a combinatorial allocation problem, and discuss some open questions related to van der Waerden's conjecture for the permanent of doubly stochastic matrices.
