The Demand Query Model for Bipartite Matching
The Demand Query Model for Bipartite Matching
复制标题
二分匹配的需求查询模型
DOI：
10.1137/1.9781611976465.36
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
N. Nisan
中科院分区：
文献类型：
--
作者：
N. Nisan
我们引入了一个“具体的复杂性”模型，用于研究二分图中的匹配算法。该模型是基于“需求查询”模型用于组合拍卖。大多数（但不是所有）已知的二分匹配算法似乎都可以转化为这个模型，包括精确，近似，顺序，并行和在线算法。二分图中的完美匹配可以在这个模型中找到O（n^{3/2}）需求查询（在每边有n个顶点的二分图中），我们主要的开放问题是提高上限或证明下限。一个改进的上限可以产生“正常”的算法，其运行时间比已知的最快的算法更好，而一个下限将排除一个更快的算法，从一个大类的算法二分匹配。我们的主要结果是找到一个近似的最大尺寸匹配并行的下限：一个确定性算法，运行在n^{o（1）}轮，其中每轮可以使最多n^{1.99}需求查询无法找到匹配的大小是在最大的n^{o（1）}因子。这与随机算法相反，随机算法可以在O（\log n）轮中找到大小为最大值的99\%$的匹配，每个轮进行n次需求查询。
We introduce a `concrete complexity' model for studying algorithms for matching in bipartite graphs. The model is based on the "demand query" model used for combinatorial auctions. Most (but not all) known algorithms for bipartite matching seem to be translatable into this model including exact, approximate, sequential, parallel, and online ones. A perfect matching in a bipartite graph can be found in this model with O(n^{3/2}) demand queries (in a bipartite graph with n vertices on each side) and our main open problem is to either improve the upper bound or prove a lower bound. An improved upper bound could yield "normal" algorithms whose running time is better than the fastest ones known, while a lower bound would rule out a faster algorithm for bipartite matching from within a large class of algorithms. Our main result is a lower bound for finding an approximately maximum size matching in parallel: A deterministic algorithm that runs in n^{o(1)} rounds, where each round can make at most n^{1.99} demand queries cannot find a matching whose size is within n^{o(1)} factor of the maximum. This is in contrast to randomized algorithms that can find a matching whose size is $99\%$ of the maximum in O(\log n) rounds, each making n demand queries.