论文标题
两部分匹配的几乎最佳沟通和查询复杂性
Nearly Optimal Communication and Query Complexity of Bipartite Matching
论文作者
论文摘要
在五个计算模型中，我们将最大核电性匹配问题（BMM）的最大双分匹配问题（BMM）的复杂性解决为多核心因素：两方通信，查询或查询，XOR查询和量子边缘查询模型。我们的结果回答了至少三十年前反复提出的公开问题[Hajnal，Maass和Turan Stoc'88； Ivanyos，Klauck，Lee，Santha和De Wolf Fsttcs'12； Dobzinski，Nisan和Oren Stoc'14; Nisan Soda'21]并拧紧了Beniamini和Nisan [Stoc'21]和Zhang [icalp'04]所示的下限。我们还解决了BMM概括的沟通复杂性，例如最高成本的两分$ b $ - 匹配和转运；以及独特的双方完美匹配的查询复杂性（回答了Beniamini [2022]的一个空旷问题）。我们的算法和下限源于已知技术的简单应用，例如切割平面方法和设置脱节。
We settle the complexities of the maximum-cardinality bipartite matching problem (BMM) up to poly-logarithmic factors in five models of computation: the two-party communication, AND query, OR query, XOR query, and quantum edge query models. Our results answer open problems that have been raised repeatedly since at least three decades ago [Hajnal, Maass, and Turan STOC'88; Ivanyos, Klauck, Lee, Santha, and de Wolf FSTTCS'12; Dobzinski, Nisan, and Oren STOC'14; Nisan SODA'21] and tighten the lower bounds shown by Beniamini and Nisan [STOC'21] and Zhang [ICALP'04]. We also settle the communication complexity of the generalizations of BMM, such as maximum-cost bipartite $b$-matching and transshipment; and the query complexity of unique bipartite perfect matching (answering an open question by Beniamini [2022]). Our algorithms and lower bounds follow from simple applications of known techniques such as cutting planes methods and set disjointness.
