Towards an optimal contention resolution scheme for matchings

• 成果类型: Article
• 署名作者: Nuti, Pranav; Vondrak, Jan
• 署名单位: Stanford University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-024-02178-w
• 发表日期: 2025
• 页码: 761-792
• 关键词: Maximization

摘要

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 xe\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$x_e$$\end{document}, we want to select a matching M subset of R(x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$M \subseteq R(x)$$\end{document} such that Pr[e is an element of M divided by e is an element of R(x)]>= c\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pr [e \in M \mid e \in R(x)] \ge c$$\end{document}, 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 optimal similar or equal to 0.544\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\simeq 0.544$$\end{document}-balanced contention resolution scheme for general matchings when & Vert;x & Vert;infinity -> 0\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Vert x\Vert _\infty \rightarrow 0$$\end{document}, and (ii) a 0.509-balanced contention resolution scheme for bipartite matchings (without any restriction on x). 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.